Доорх тэгшитгэлийн хувьд:

Тэмдэглэлгээ [$a$] нь $a$ тооны бүхэл хэсэг юм.

Тухайн тэгшитгэл эерэг бүхэл тоон шийдгүй байхаар бүх бүхэл $z$ ($z > 0$) -үүдийг ол. Эерэг бүхэл тоон шийдгүй байна гэдэг нь дээрх тэгшитгэлийг хангах эерэг бүхэл $x$, $y$ ($x, y > 0$) олдохгүй байна гэсэн үг.

Тэгвэл бүх дээрх нөхцөлийг хангах z үүдийг өсөх эрэмбээр бичье $z_1$, $z_2$, $z_3$ гэх мэт ($z_i$ $<$ $z_{i + 1}$). Тэгвэл чиний даалгавар $n$ өгөгдсөн бол $z_n$ -ийг ол.

Оролт

Эхний мөрөнд нэг бүхэл тоо $n$ ($1 ≤ n ≤ 40$) өгөгдөнө.

Гаралт

Хариу болох $z_n$-ийн $1000000007$ ($10^9 + 7$) хуваахад гарсан үлдэгдлийг хэвлэ.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.