Masala #0343

Xotira 32 MB Vaqt 1000 ms
14

Toqlar Yig’indisi

Sizga uzunligi \(N+1\) bo'lgan \(A [A_0, A_1, A_2, \dots , A_n]\) massivi berilgan. \(A_0=0\), \(A_1=1\)  va qolgan elementlari o'zidan oldingi 2 ta elementning yig'indisiga teng bo'lsa \(A\) massivning toq o'rinda turgan barcha hadlari yig'indisining \(10^9+7\) ga bo'lgandagi qoldig’ini toping.


Kiruvchi ma'lumotlar:

Sizga \(n(1 \le n \le 10^{17})\) soni beriladi.


Chiquvchi ma'lumotlar:

Masala javobini chop eting.


Misollar
# input.txt output.txt
1
3
3