Masala #TW73WHEDWQ

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 1 %
14

  

Sehrli metall

Ajoyib fantaziya olamida sehrli xususiyatlarga ega noyob metalllar bilan mashhur bo‘lgan qadimiy alkimyoviy doira mavjud. Har bir metall maxsus kuchga ega va sirli jarayon orqali boshqa metallga aylanishi mumkin.

Dastlab, faqat ikkita metall bor: Metall X va metall Y. Ketma-ketlikdagi har bir keyingi metall maxsus alkimyoviy formuladan foydalangan holda oldingi ikkita metallni birlashtirish orqali olinadi. Sehrgarlar har bir yangi metalldagi sehrli energiya miqdori avvalgi ikkita metallning sehrli energiyasi yig‘indisiga to‘liq teng ekanligini aniqladilar.

Sizning vazifangiz n-metallni miqdorini \(10^9\)+7 ga bo'lgandagi qoldiqni topishdan iborat


Kiruvchi ma'lumotlar:

Yagona qatorda N (1 ≤ N ≤ 10^18) soni.


Chiquvchi ma'lumotlar:

N-sehrli metall miqdorini \(10^9+7\) ga bo'lgandagi qoldiqni chop eting.


Misollar
# input.txt output.txt
1
1
1
2
4
5
3
6
13
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin