Zapina

Υπάρχουν συνολικά ~N~ νέοι προγραμματιστές που προετοιμάζονται για το δεύτερο μέρος της αγωνιστικής σεζόν κατά τη διάρκεια χειμερινής κατασκήνωσης στην Ζάγκρεμπ. Ο κύριος Malnar, μεγάλος υποστηρικτής της τάξης, της πειθαρχίας και της σκληρής δουλειάς, είπε στους προγραμματιστές να σχηματίσουν μια γραμμή και έδωσε στον καθένα έναν ορισμένο αριθμό (πιθανόν μηδέν) εργασιών. Αυτός έδωσε συνολικά N διαφορετικές εργασίες και ξέρει ότι ο i-οστός προγραμματιστής στη σειρά θα είναι ευχαριστημένος αν πάρει ακριβώς ~i~ εργασίες.

Με πόσους διαφορετικούς τρόπους θα μπορούσε ο κ. Malnar να δώσει τις εργασίες με τέτοιο τρόπο ώστε τουλάχιστον ένας προγραμματιστής να είναι ευχαριστημένος; Δύο τρόποι απόδοσης των εργασιών θεωρούνται διαφορετικοί εάν υπάρχει ένας προγραμματιστής και μια εργασία ώστε με τον έναν τρόπο ο προγραμματιστής να πάρει την εργασία ενώ με τον άλλο να μην την πάρει.

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο αριθμό ~N\;(1 \le N \le 350)~.

Έξοδος

Τυπώστε τον αριθμό τρόπων που αναζητήσατε στη μορφή υπολοίπου ακέραιας διαίρεσης με το ~10^9 + 7~.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	22	~1 \le N \le 7~
2	33	~1 \le N \le 20~
3	55	Κανένας επιπλέον περιορισμός.

Παραδείγματα

input

1

output

1

input

2

output

3

Επεξήγηση του 2ου παραδείγματος:

Τρόποι για να δώσεις τις εργασίες στις οποίες τουλάχιστον ένας προγραμματιστής είναι ευχαριστημένος είναι:

1. Πρώτη εργασία στον πρώτο προγραμματιστή, δεύτερη εργασία στον δεύτερο.

2. Δεύτερη εργασία στον πρώτο προγραμματιστή, πρώτη εργασία στον δεύτερο.

3. Και οι δύο εργασίες στον δεύερο προγραμματιστή.

input

314

output

192940893