Masala #1171

Xotira 16 MB Vaqt 1000 ms
14

Shifr

Tizim mustahkamligini ta'minlash maqsadida tizimda yangi shifrlash algoritmi ishlab chiqildi.

Unda 4 ta \(A, B, C, D\) belgilar qatnashishi mumkin. Faqat bunda bir nechta shartlar mavjud:

  • Ikkita bir xil belgi yonma-yon bo'lmasligi kerak.
  • \(A\) va \(D\) belgilari yonma-yon bo'la olmaydi.
  • B va C belgilar yonma-yon bo'la olmaydi.
  • BAC yoki CAB ko'rinishidagi qism satr ham mavjud bo'lmasligi kerak.
  • Simmetrik shifrlar bir xil shifrlar deb hisoblanadi. Ya'ni ABC vs CBA bitta shifr hisoblanadi.

Sizning vazifangiz \([L, R]\) uzunlikda nechta yuqoridagi shifrlarni qanoatlantiruvchi shifrlar mavjudligini aniqlash.


Kiruvchi ma'lumotlar:

Kirish faylida 2 ta natural son \(L, R\) beriladi. \(L, R \le 10^9\)


Chiquvchi ma'lumotlar:

Chiqish faylida masala javobini \(1000000007\) ga bo'lgandagi qoldiqni chop eting.


Misollar
# input.txt output.txt
1
3 4
23
2
5 6
64
3
3 3
11
Izoh:

1-test:

Uzunligi 3 bo'lgan shifrlar:

BAB, BDB, BDC, CAC, CDC, ABA, ABD, ACA, ACD, DBD, DCD

Uzunligi 4 bo'lgan shifrlar:

BABA, BABD, BDBA, BDBD, BDCA, BDCD, CACA, CACD, CDBA, CDBD, CDCA, CDCD