Masala #0211

Xotira 16 MB Vaqt 1000 ms
14

Satr

Quyidagi shartlarni qanoatlantiruvchi S satrlar sonini toping:

  • S satr uzunligi N ga teng;
  • S satr elementlari faqatgina s,a,t,r harflaridan iborat;
  • S satrdagi s harfi juft marotaba qatnashgan;
  • S satrdagi t harfi juft marotaba qatnashgan.

DIQQAT: juft marotaba qatnashish deganda 0 marotaba  qatnashish ham inobatga olinadi.

n=1 da S satr a yoki r bo`lishi mumkin. Ya`ni yuqoridagi shartlarni qanoatlantiruvchi 2 ta satr mavjud.

n=2 bo`lganda S satr quyidagilar bo’lishi mumkin ss, tt, ra, ar, aa, rr.

Demak n=2 da S satrlar soni 6 ta.


Kiruvchi ma'lumotlar:

Kirish faylida bitta natural son N(1 ≤ N ≤ 109) kiritiladi.


Chiquvchi ma'lumotlar:

Chiqish fayliga berilgan shartni qanoatlantiruvchi S satrlar sonining 109+7 ga bo’lgandagi qoldig’ini chop eting.


Misollar
# input.txt output.txt
1
1
2
2
2
6