E. Тачибана Канадэ-ийн дүпү

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

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

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

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

Тачибана Канадэ мапу дүпүд үнэхээр дуртай. Нэгэн өдөр цайны газар бүх төрлийн дүпүг зарахаар бэлтгэжээ. Гэхдээ бүх дүпү нь мапу дүпү биш ба хангалттай халуун амттай хэдийг нь л мапу дүпү гэж нэрлэж болно.

Цайны газрын зүсэм дүпү бүр нь $m$-суурьт тоогоор өгөгдөх ба бүх тоонууд нь $[l, r]$ завсарт байна ($l$ болон $r$ нь $m$-суурьт тоонууд байна). $[l, r]$ завсар дахь $m$-суурьт тоо бүрийн хувьд ийм дугаартай зүсэм дүпү оршин байна. ($m$-суурьт тоо гэдэг нь $m$-тын тооллын системийн тоог хэлнэ)

Ямар дүпү нь мапу дүпү болохыг ялгахын тулд, Тачибана Канадэ $n$ ширхэг $m$-суурьт тоон тэмдэгт мөрүүдийг сонгох ба тэмдэгт мөр болгон нь ямар нэг утгатай байна. Хэрэв тэмдэгт мөр нь ямар нэгэн дүпүний дугаар дотор гарч ирвэл уг тэмдэгт мөрийн утгыг тухайн дүпүний утга дээр нэмнэ. Хэрэв тэмдэгт мөр нь олон удаа гарч ирвэл утга нь мөн л тийм хэмжээний удаа утгыг нь нэмэх юм. Анхандаа бүх дүпү нь 0 гэсэн утгатай байна.

Тачибана Канадэ $k$-аас ихгүй утгатай дүпүнүүдийг мапу дүпү гэж үзнэ. Одоо Тачибана Канадэ хэчнээн зүсэм дүпү нь мапу дүпү болохыг мэдэхийг хүсжээ?

Оролт

Эхний мөрөнд 3 бүхэл тоо $n$, $m$ болон $k (1 ≤ n ≤ 200; 2 ≤ m ≤ 20; 1 ≤ k ≤ 500)$ өгөгдөнө. Энд $n$ нь тэмдэгт мөрийн тоог, $m$ нь хэрэглэгдэх суурийн тоог, $k$ нь мапу дүпүгийн утгын хязгаарыг илэрхийлнэ.

2-дахь мөрөнд $l$ тоог дүрсэлнэ. Уг мөрийн эхний бүхэл тоо $len$ $(1 ≤ len ≤ 200)$ нь $l$-ын уртыг ($m$ суурь дахь цифрүүдийн тоо) илэрхийлнэ. Дараа нь $len$ ширхэг бүхэл тоо $a_{1}, a_{2}, ..., a_{len} (0 ≤ a_{i} < m; a_{1} > 0)$-ууд зайгаар тусгаарлагдан өгөгдөх ба эдгээр нь $l$-ын цифрүүдийг илэрхийлнэ. $a_{1}$ нь хамгийн их цифр ба $a_{len}$ нь хамгийн бага цифр байна.

3-дахь мөрөнд $r$ тоог $l$-тэй адил хэлбэрээр дүрсэлнэ. Мөн $1 ≤ l ≤ r$ байна.

Дараагийн $n$ мөрийн мөр болгонд тоон тэмдэгт мөрүүдийг дүрсэлнэ. $i$-дахь мөрөнд $i$-дахь тоон тэмдэгт мөр болон уг тэмдэгт мөрийн утга болох $v_{i}$ ($1 ≤ v_{i} ≤ 200$) өгөгдөнө. Бүх тоон тэмдэгт мөрүүд нь бараг $l$-тэй ижил хэлбэрээр өгөгдөх ба ганц ялгаа нь тоон тэмдэгт мөрүүд нь 0-ээр эхлэх хэрэггүй (эхний жишээг харна уу). Бүх тоон тэмдэгт мөрүүдийн уртуудын нийлбэр $200$-оос хэтрэхгүй.

Гаралт

Мапу дүпүгийн зүсмийн тоог $1000000007$ $(10^{9} + 7)$ модулаар бодон хэвлэнэ үү. Хариулт нь аравтын тооллын бүхэл тоо байна.

Орчуулсан: Баатархүү

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

Оролт
2 10 1
1 1
3 1 0 0
1 1 1
1 0 1
Гаралт
97
Оролт
2 10 12
2 5 9
6 6 3 5 4 9 7
2 0 6 1
3 6 7 2 1
Гаралт
635439
Оролт
4 2 6
6 1 0 1 1 1 0
6 1 1 0 1 0 0
1 1 2
3 0 1 0 5
4 0 1 1 0 4
3 1 0 1 2
Гаралт
2

Тэмдэглэл

Эхний жишээнд бүх үйлдлийг хийсний дараа $[1, 100]$ завсарт байх 1-ээс их утгатай 10, 11 болон 100 гэсэн зөвхөн 3-н ширхэг 10-тын тоо байна. Энд байгаа 1-ын утга нь 1 бөгөөд 2 биш юм. Тоонууд нь 0-ээр эхэлж болохгүй учраас "$01$" гэж бичигдэж болохгүй.

2-дахь жишээнд уг завсарт өгөгдсөн ямар ч тоонууд нь 12-оос их утгатай байна.

3-дахь жишээнд өгөгдсөн завсарт байх 6-аас ихгүй утгатай 110000 болон 110001 гэсэн зөвхөн 2 ширхэг 2-тын тоо байна.

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