Masala #0251

Xotira 16 MB Vaqt 1000 ms
14
Muallif: Sirojiddin

Fraktal

Asadullo fraktal shakllarga qiziqadi. U yangi fraktal shakl o’ylab topdi va uni quyidagi tartibda to’ldira boshladi:

  • 1-qadamda Asadullo \(R\) radiusli aylana chizib oldi.
  • 2-qadamda 1-qadamda chizilgan aylananing atrofida 3 ta kvadrat chizdi
  • 3-qadamda 2-qadamda chizilgan kvadratlarning to’rttala qirrasida ham aylana chizdi
  • \(2*k\) – qadamda \(2*k-1\) – qadamda chizilgan aylanalarning atrofida 3 tadan kvadrat chizdi
  • \(2*k+1\) – qadamda \(2*k\) – qadamda chizilgan kvadratlarning to’rttala qirrasida ham aylana chizdi

1-bosqich

2-bosqich

3-bosqich

 

Asadullo ushbu fraktal shaklning \(N\)-qadamigacha chizib chiqish murakkab ekanligini, lekin, \(N\)-qadamgacha jami nechta shakl chizilganini (aylana va kvadratlar) aniqlash mumkinligini  tushunib yetdi. Asadulloga \(N\)-qadamgacha chizilgan shakllar sonini aniqlashda yordam bering.


Kiruvchi ma'lumotlar:

Kirish faylida yagona butun son, \(N(1 ≤ N ≤ 10^{18)}\) soni kiritiladi.


Chiquvchi ma'lumotlar:

Chiqish faylida yagona son, \(N\)-qadamigacha chizilgan shakllar umumiy sonini \(1000000007(10^9+7)\) ga bo’lgandagi qoldiqni chop eting!


Misollar
# input.txt output.txt
1
1
1
2
2
4
3
3
16