Masala #1171

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 55 %

#Dinamik dasturlash

#Matematika

#Matrix

Muallif: Qarshiyev Asadbek

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

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

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin