F. Пи тооны цифрүүд

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

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

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

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

Васили саяхан $π$ тооны тухай гайхалтай нэгэн чанарыг сурсан. өгүүллүүдийн нэгэнд нь бидэнд байгаа ямар ч тоонуудын дараалал $π$ тооны цифрүүдийн дунд ямар нэг байрлалд байгааг таамаглачихсан байсан. Иймээс хэрвээ та жишээлбэл Оросын зохиолч Лео Толстойгийн "Дайн ба Энх" нобелийн шагналт туужийг авч тоогоор шифрлэе тэгвэл бид $π$ тооны тэмдэгтүүдээс нобелийг олох болно.

Васили үүнд туйлын баярласан учир нь бүх ном, дуунууд болон программууд бичигдсэн ба $π$ тооны цифрүүд дунд кодлогдсон. Мэдээж Васили үүнд бага зэрэг сэрэмжтэй байгаа учир нь энэ зүгээр л таамаг ба батлагдаагүй иймээс тэр үүнийг шалгахаар шийдсэн.

Үүнийг хийхийн тулд Васили интернетеес $π$ тооны цифрүүдийн дарааллийг архивласан файлыг татаж авсан, тодорхой байрлалаас эхлээд татаж авсан архив файлд байх ялгаатай цифрүүдийн тэмдэгт мөрүүдийг шалгаж эхэлсэн. Васили цифрүүдийн богино тэмдэгт мөрүүдийг хурдан олсон, гэвч урт тэмдэгт мөр авах болгонд архив файлд энэ нь байхгүй байгаад байв. Васили хэрэв архив файлд агуулагдаж байгаа ядаж урттай дэд тэмдэгт мөрийг агуулж байгаа $d$ урттай тэмдэгт мөр байвал хагас тохиолдож байна гэх тодорхойлолттой болж ирсэн.

Судалгаагаа дуусгахын тулд Васили $2$ том тоо болох $x, y$ ($x ≤ y$) сонгосон ба хоёр тооны цифрүүдийн тоо тэнцүү ба одоо тэр $x$-c $y$ хоорондох архив файлд хагас тохиолтой тоонуудын тоог олохыг хүсч байна. Василид уг утгыг $10^{9} + 7$ тоонд хуваагаад гарсан үлдэгдлийг тооцоолоход туслана уу.

Оролт

Эхний мөрөнд Василигийн дэд тэмдэгт мөрүүдийг хайхад ашиглах аравтын цифрүүдээс бүрдэх $s$ тэмдэгт мөр байна. Таамгаар бол энэ цифрүүдийн дараалал нь $π$ тооны аравтын илэрхийлэл дотор байх боловч бид үүнийг батлаж чадахгүй.

Хоёр дахь болон гурав дахь мөрөнд ижил $d$ ($x ≤ y$, $2 ≤ d ≤ 50$) урттай хоёр эерэг бүхэл тоонууд $x, y$ байна. $x, y$ тоонууд нь тэгээр эхлэхгүй.

Гаралт

$x$-c $y$-н хоорондох хэсэгт хагас тохиолтой тоонуудын тоог $10^{9} + 7$ тоонд хуваагаад үлдэгдлийг хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
02
10
19
Гаралт
2
Оролт
023456789
10
19
Гаралт
9
Оролт
31415926535
10
29
Гаралт
20
Сэтгэгдлүүдийг ачааллаж байна...