Masala #0211

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.

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

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