Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
D. Морины уралдаан
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Петягийн ихэд дурладаг морины уралдаанд $l$-ээс $r$ хүртэл дугаартай моринууд нэг дор уралддаг. Петя түрүүлэх магадлалтай морьнуудыг тодорхойлохыг хүсэв. Тэгээд тодорхой шалтгааны улмаас "бараг азын дугаар"-тай морьнуудын тоог мэдэхийг хүсэв. "Бараг азын дугаар" гэдэг нь аравтын бичиглэлд нь ядаж хоёр азын цифр $k$-аас хэтрэхгүй зайтай байрлаж орсон тоог хэлнэ.
Петя Львов дахь найзаасаа $4$ ба $7$ бол азын цифрүүд гэдгийг мэдэж авсан бөгөөд цифрүүдийн хоорондын зай гэдэг нь цифрүүдийн байрлалыг илэрхийлэх дугааруудын ялгаварыг тооцно.
Жишээ нь $k = 2$ үед $412395497$, $404$, $4070400000070004007$ тоонууд нь бараг азын дугаар болох ба $4$, $4123954997$, $4007000040070004007$ тоонууд нь биш.
Петя $t$ ширхэг $[l_i, r_i]$ завсар бэлтгэсэн ба $k$ тоог тооцоолж олжээ. Одоо танаас хүсч байгаа түүний хүсэлт бол завсар бүр дэхь бараг азын дугаарын тоог олох юм. Хариу хэт их гарж болзошгүй тул $1000000007$-д ($10^9+7$) хуваасан үлдэгдлийг Петяд мэдээллэхэд болно.
Оролт
Эхний мөрөнд $t$ ба $k$ ($1 ≤ t, k ≤ 1000$) хоёр тоо. Дараагийн $t$ мөрөнд мөр бүрд $l_i$, $r_i$ ($1 ≤ l ≤ r ≤ 10^{1000}$) тоонууд зайгаар тусгаарлагдан өгөгдөнө. Оролтын өгөгдөл дэхь тоонууд зөв бичиглэлтэй буюу тэгээр эхлэхгүй.
Гаралт
$t$ мөрөнд мөр бүрт хариу болох тоог $1000000007$-д ($10^9+7$) хуваасан үлдэгдэл байна.
Орчуулсан: gmunkhbaatarmn
Жишээ тэстүүд
Оролт
1 2 1 100
Гаралт
4
Оролт
1 2 70 77
Гаралт
2
Оролт
2 1 1 20 80 100
Гаралт
0 0
Тэмдэглэл
In the first sample, the four nearly lucky numbers are 44, 47, 74, 77.
In the second sample, only 74 and 77 are in the given segment.