Parovi

Ο Mirko και ο Slavko παίζουν ένα παιχνίδι. Η σειρά του Mirko είναι πρώτη και επιλέγει ένα μη-κενό σύνολο ζευγών αριθμών μεταξύ ~1~ και ~N~ (κλειστό διάστημα) υπό την προϋπόθεση ότι οι αριθμοί που αποτελούν ένα ζεύγος είναι αμοιβαία σχετικά πρώτοι. Οι αριθμοί που αποτελούν ένα ζευγάρι πρέπει να είναι διαφορετικοί. Για παράδειγμα, για ~N\;=\;5~, ο Mirko θα μπορούσε να έχει επιλέξει το ακόλουθο σύνολο ζευγών: ~\{\{1,\;2\},\;\{3,\;4\},\;\{2,\;5\},\;\{3,\;5\}\}~.

Η σειρά του Slavko είναι δεύτερη και ο στόχος του είναι να βρει μια διαμέριση για τα ζευγάρια του Mirko. Το σύνολο ζευγών του Mirko έχει μια διαμέριση εάν υπάρχει ένας ακέραιος ~x~ από το σύνολο ~\{2,\;3,\;\ldots,\;N\}~ έτσι ώστε, για κάθε ζεύγος ~\{a,\;b\}~, ισχύει ένα από τα ακόλουθα:

• ~a, b < x~
• ~a, b \ge x~

Για παράδειγμα, ένα σύνολο ζευγών ~\{\{1,\;2\},\;\{3,\;4\}\}~ έχει μια κατάτμηση ~x\;=\;3~. Εάν υπάρχει ένα διαμέρισμα, ο Slavko σίγουρα θα το βρει.

Ο Mirko κερδίζει αν ο Slavko δεν μπορεί να βρει ένα διαμέρισμα για το σετ του. Προσδιορίστε πόσα διαφορετικά σετ ζευγαριών υπάρχουν που μπορεί να επιλέξει αρχικά ο Mirko και να είστε σίγουροι για τη νίκη του. Δεδομένου του γεγονότος ότι ο συνολικός αριθμός των συνόλων μπορεί να είναι πολύ μεγάλος, εξάγετε τον αριθμό modulo ~1\,000\,000\,000~.

Είσοδος

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

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον απαιτούμενο αριθμό.

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

input

2

output

1

Επεξήγηση του 1ου παραδείγματος: Το μόνο σύνολο ζευγών που πληροί τις δεδομένες απαιτήσεις είναι το ~\{\{1,\;2\}\}~.

input

3

output

5

Επεξήγηση του 2ου παραδείγματος: Ένα παράδειγμα συνόλου που πληροί τις δεδομένες απαιτήσεις είναι τα ~\{\{1,\;3\},\;\{1, 2\}\}~.

input

4

output

21