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.

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