Masala #0875

Xotira 128 MB Vaqt 1000 ms
14

Xarid

Sizda 1 so'mlik, 2 so'mlik, 4 so'mlik va h.k 2 ning darajalaridan iborat cheksiz tangalar mavjud. Siz N so'mlik mahsulotni bu tangalar yordamida necha xil usulda xarid qilishingiz  mumkin ?


Kiruvchi ma'lumotlar:

Kirish faylining yagona satrida bitta butun son N soni kiritiladi \((1 \leq N \leq 2 * 10^6)\)


Chiquvchi ma'lumotlar:

Chiqish faylida yagona butun son, ya'ni masala javobini chop eting. Bu son juda katta bo'lishi mumkin shuning uchun siz uni 1000000007 ga bo'lgandagi qoldig'ini chiqaring.


Misollar
# input.txt output.txt
1
5
4
Izoh:

Namunada 5 so'mlik mahsulotni 4 xil usul deganda {1, 1, 1, 1, 1}, {1, 1, 1, 2}, {1, 2, 2},. {1, 4} usullar nazarda tutilgan.  {1, 4} va {4, 1} bir xil usul deb qaralsin.