Πλησιάζουν οι γιορτές στον βυθό και συνεπώς ο Μίλτος το δελφίνι έχει σκοπό να κεράσει τους φίλους του για την πρωτοχρονιά. Δυστυχώς, το θυμήθηκε τελευταία στιγμή και δεν πρόλαβε να φτιάξει βασιλόπιτα. Αντί γι' αυτό, αγόρασε μια σοκολάτα με n κομμάτια και για καλή του τύχη οι φίλοι του τυχαίνει να είναι ακριβώς n στο πλήθος. Ο Μίλτος θέλει να τους κεράσει όλους σοκολάτα, οπότε αποφάσισε να προσφέρει στον καθένα από 1 κομμάτι ( η σοκολάτα είναι μια γραμμή μεγέθους n ). Για να το κάνει αυτό, ο Μίλτος εκτελεί την εξής διαδικασία: έχοντας την σοκολάτα πάνω στο τραπέζι, την κόβει σε κάποιο τυχαίο σημείο. Έπειτα, διαχωρίζει τα δύο κομμάτια που προέκυψαν και εκτελεί την ίδια διαδικασία για το καθένα ξεχωριστά. Στο τέλος αυτής της διαδικασίας, προκύπτουν n κομμάτια σοκολάτας.
Ο Μίλτος εκτέλεσε αυτή την διαδικασία με επιτυχία και προσέφερε τα κομμάτια στους φίλους του. Αμέσως όμως μετά προέκυψε το εξής ερώτημα που τον απασχόλησε καθ' όλη την διάρκεια της νύχτας. Με πόσους δυνατούς τρόπους θα μπορούσε να εκτελέσει την διαδικασία αυτή; Μπορείς να βοηθήσεις τον Μίλτο να απαλλαγεί από αυτό το ερώτημα και να απολαύσει το υπόλοιπο της νύχτας του;
Ένας φυσικός αριθμός n που αναπαριστά το μέγεθος της σοκολάτας.
Ένας ακέραιος αριθμός Α, το πλήθος των δυνατών τρόπων με τους οποίους ο Μίλτος μπορεί να κόψει την σοκολάτα. Επειδή το πλήθος αυτό μπορεί να είναι πολύ μεγάλο να εκτυπωθεί modulo 1000000007.
Για το 30% των δεδομένων εισόδου θα είναι 1 <= n <= 18
Για το 80% των δεδομένων εισόδου θα είναι 1 <= n <= 10000
Για το 100% των δεδομένων εισόδου θα είναι 1 <= n <= 1000000
3
2