Masala O
IDTK
Bitboy IDTK(Ikkining Darajalaridan Tuzilgan Ketma-ketlik)ni juda yaxshi ko'radi. Uning tug'ilgan kuniga otasi Baytboy \(2^N\) sonini sovg'a qildi. Bu sonni Bitboy o'zi uchun tuzmoqchi bo'lgan IDTK ning dastlabki (va hozircha yagona) elementi qilib oldi.
Bitboy ixtiyoriy vaqtda o'zining IDTKi ichiga quyidagicha o'zgartirish kiritishi mumkin:
- IDTK ichidan qiymati \(K (K > 1)\) ga teng bo'lgan ixtiyoriy sonni tanlab uning o'rniga shu sonni ikkiga bo'lingan qiymatidan 2 ta ya'ni \(K/2\), \(K/2\) ni joylashtirishi mumkin.
- IDTK ichidan qiymati \(K (K > 2)\) ga teng bo'lgan ixtiyoriy sonni tanlab uning o'rniga\(K/4\), \(K/2\), \(K/4\) ni joylashtirishi mumkin.
Shuni esda saqlash kerakki, Bitboy IDTK dagi qiymatlarning o'rnini o'zgartira olmaydi.
Bitboyning odatlarini juda yaxshi bilgan Baytboy o'g'liga bergan \(2^N\) soni oradan vaqtlar o'tib qanday ketma-ketlik bo'lishi mumkinligi haqida qiziqib qoldi. O'ylab qarasa bo'lishi mumkin bo'lgan ketma-ketliklar soni juda ko'p ekan. Shu sababli u bo'lishi mumkin bo'lgan ketma-ketliklar sonini topmoqchi. Unga buni aniqlashda yordam bering.
Kirish faylida yagona butun son, \(N(0 \le N \le 10^7)\) soni kiritiladi.
Baytboy aniqlamoqchi bo'lgan qiymatni \(10^9 + 9\) ga bo'lgandagi qoldiqni chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
2 |
6 |
| 2 |
4 |
2350 |
1-test:
\(N=2\)
Baytboy sovg'a qilgan son \(2^N=2^2=4\)
| yakuniy holat | Kelib chiqish bosqichlari | |
| 1 | [4] | [4] |
| 2 | [2,2] | [4]->[2,2] |
| 3 | [1,1,2] | [4]->[2,2]->[1,1,2] |
| 4 | [2,1,1] | [4]->[2,2]->[2,1,1] |
| 5 | [1,2,1] | [4]->[1,2,1] |
| 6 | [1,1,1,1] | [4]->[2,2]->[1,1,2]->[1,1,1,1] |
| [4]->[2,2]->[2,1,1]->[1,1,1,1] | ||
| [4]->[1,2,1]->[1,1,1,1] |
Telegram kanalimizga obuna bo'ling