Паша саяхан $jPager$ гэх шинэ утас худалдаж авсан ба найзуудынхаа утасны дугааруудыг үүн дээрээ нэмж эхлэсэн. Утасны дугаар бүр яг $n$ тооноос бүрдэнэ.

Мөн Пашад $k$ тоо байгаа ба $n / k$ ($n$ нь $k$-д хуваагдана) урттай хоёр дараалал болох $a_{1}, a_{2}, ..., a_{n / k}$ болон $b_{1}, b_{2}, ..., b_{n / k}$ байгаа. Утасны дугаарыг $k$ урттай блокуудад хуваацгаая. Эхний блок утасны дугаарын $1$, $2$,..., $k$ байрлалууд дээр байгаа цифрүүдээс бүрдэх бол хоёрдугаар блок утасны дугаарын $k + 1$, $k + 2$, ..., $2*k$ байрлалууд дээр байгаа цифрүүдээс бүрдэнэ энэ маягаар цааш хуваагдана. Паша хэрвээ $i$-р блок $b_{i}$ цифрээр эхлээгүй мөн блокыг бүхэл тоо хэлбэрээр илэрхийлэхэд $a_{i}$-д хуваагдаж байвал уг утасны дугаарыг гоё гэж үздэг.

$n$ урттай блокыг бүхэл тоо хэлбэрээр илэрхийлэхийн тулд үүнийг $c_{1}$, $c_{2}$,...,$c_{k}$ дараалал хэлбэрээр бичье. Ингээд бүхэл тоон утга нь $c_{1}*10^{k - 1} + c_{2}*10^{k - 2} + ... + c_{k}$ илэрхийллийн үр дүнтэй тэнцүү.

Паша таныг өгөгдсөн $k$, $a_{i}$, $b_{i}$-уудын хувьд $n$ урттай хэдэн гоё утасны дугаар байгааг олохыг хүсч байна. Энэ тоо их байж болох тул $10^{9} + 7$ тоонд хуваагаад үлдэгдлийг хэвлэнэ үү.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $k$ ($1 ≤ n ≤ 100 000$, $1 ≤ k ≤ min(n, 9)$) байх ба харгалзан бүх утасны дугааруудын урт болон блок бүрийн урт юм. $n$ тоо нь $k$-д хуваагдана.

Оролтын хоёр дахь мөрөнд зайгаар тусгаарлагдсан $n / k$ ширхэг эерэг бүхэл тоон утгууд болох $a_{1}, a_{2}, ..., a_{n / k}$ ($1 ≤ a_{i} < 10^{k}$) дараалал байна.

Оролтын гурав дахь мөрөнд зайгаар тусгаарлагдсан $n / k$ ширхэг эерэг бүхэл тоон утгууд болох $b_{1}, b_{2}, ..., b_{n / k}$ ($0 ≤ b_{i} ≤ 9$) дараалал байна.

Гаралт

$n$ урттай гоё утасны дугааруудын тоог $10^{9} + 7$ тоонд хуваагаад үлдэгдэл болох нэг ширхэг бүхэл тоон утгыг хэвлэнэ.

Эхний жишээн дээр гоё утасны дугаарууд нь: $000000$, $000098$, $005600$, $005698$, $380000$, $380098$, $385600$, $385698$.