D. Далбаа

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Игорийг нэгдүгээр курсэд байхад профессор нь түүнийг болон тэдний ангийнханыг олимпиадын програмчлалыг шийдвэрлэхийг хатуу шаарддаг байжээ. Нэг өдөр “Тиммигийн Онлайн Шүүгч” нэртэй вэб сайтын "Далбаа" хэмээх бодлого түүний анхаарлыг ихэд татжээ. Бодлогын даалгавар нь өгөгдлийн дагуу шаардлагад нийцсэн гурван өнгийн далбаануудын тоог олох явдал байв ч... энэ нь үнэндээ хамааралгүй зүйл юм. Игор томъёог хурдхан олоод “Хариуг хүлээн авлаа” гэж сонсохыг тэсч ядан хүлээж байв.

Гэсэн хэдий ч энэ нь профессорыг тийм ч их гайхшруулсангүй. Түүнд “Тиммигийн Онлайн Шүүгч” вэб сайт дээр гарсан бодлого хоёрхон хязгаартай, далбааны судалд орох гуравхан боломжит өнгөтэй маш энгийн, уйтгартай санагдав. Ингээд Игорт нэгэн төвөгтэй бодлого өгсөнөөр тэр хариуг олж чадсангүй. Мэдээж хэрэг бид профессор өөрөө ч энэхүү бодлогын хариуг олж чадахгүй байгааг хэнд ч хэлэхгүй.

Харин та энэ бодлогын хариуг олж чадах уу?

Далбаанууд нэг өнгөнөөс эсвэл ижил өргөнтэй хэд хэдэн судалнаас бүрдсэн байна. Судалнууд дараах өнгөнүүд байж болно: цагаан, хар, улаан, шар. Та $L$-ээс $R$ хооронд судлуудын тоотой хэдэн өөр хоорондоо адилгүй далбаануудын тоог олно. Гэхдээ:

  • Далбаа нь нэг өнгийн зэрэгцээ судалтай байж болохгүй;

  • Далбаа цагаан, шар өнгийн зэрэгцээ судалтай байж болохгүй;

  • Далбаа улаан, хар өнгийн зэрэгцээ судалтай байж болохгүй;

  • Далбаа хар, цагаан, улаан өнгийг энэ дарааллаар болон урвуу дарааллаар хослуулсан судалтай байж болохгүй;

  • Тэгш хэмтэй далбаа ч мөн адил боломжгүй (жишээ нь: цагаан хар эсвэл хар, цагаан гэсэн хоёр өнгөнөөс бүрдсэн далбаа)

Оролт

Энэхүү ганц мөр нь $L$ болон $R$ ($1 ≤ L ≤ R ≤ 10^{9}$) гэсэн хоёр бүхэл тоог агуулж байна. Энэ нь далбаан дээр байх судалнуудын дээд болон доод хязгаарыг илэрхийлсэн тоо юм.

Гаралт

Бодлогын нөхцлийг хангахуйц, өөр хоорондоо ялгаатай, $L$-ээс $R$-ын хооронд судлуудтай, $1000000007$ модультай далбаануудын тоог ол.

Орчуулсан: Энхгэрэл

Жишээ тэстүүд

Оролт
3 4
Гаралт
23
Оролт
5 6
Гаралт
64

Тэмдэглэл

Эхний туршилтаар дараах далбаанууд байж болох юм. (толь зүйн дарааллаар дараах байдлаар жагсааж болох юм. Х-хар, У-улаан, Ц-цагаан, Ш-шар гэж товчилъё.)

3 судалтай: ХЦХ, ХШХ, ХШУ, УЦУ, УШУ, ЦХЦ, ЦХШ, ЦУЦ, ЦУШ, ШХШ, ШУШ (нийт 11 далбаа).

4 судалтай: ХЦХЦ, ХЦХШ, ХШХЦ, ХШХШ, ХШУЦ, ХШУШ, УЦУЦ, УЦУШ, УШХЦ, УШХШ, УШУЦ, УШУШ (12 далбаа).

Иймд эхний жишээний хариулт $11 + 12 = 23$ болно.

Сэтгэгдлүүдийг ачааллаж байна...