Masala #0875
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 ?
Kirish faylining yagona satrida bitta butun son N soni kiritiladi \((1 \leq N \leq 2 * 10^6)\)
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.
# | input.txt | output.txt |
---|---|---|
1 |
5 |
4 |
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.