Цифрүүдээс бүрдэх $b$ блокууд байна. Блок бүр ижилхэн байх ба танд оролтонд өгөгдөх $n$ ширхэг тогтмол цифрүүдээс бүрдэнэ. Вэт Шарк блок бүрээс яг нэг цифр сонгох ёстой ба уг цифрүүдээ хооронд нь холбож нэг ширхэг бүхэл тоо үүсгэнэ. Жишээлбэл, хэрвээ тэр эхний блокоос $1$ цифрийг сонгож хоёр дахь блокоос $2$ гэсэн цифрийг сонгосон бол тэр $12$ гэсэн тоотой болно гэсэн үг.

Вэт Шарк уг тоог $x$ тоонд хуваагаад үлдэгдлийг авна. Түүнд $k$ тоог гарган авахын тулд блок бүрээс нэг цифрийг хэдэн янзаар авч болох вэ гэдгийг хэлж өгнө үү. Хариу болох тоо маш их байж болох учир уг тоог $10^{9} + 7$ тоонд хуваагаад үлдэгдлийг хэвлэ.

Нэг блокоос нэг цифрийг сонгох боломжийн тоо нь уг блокт уг цифр хэдэн ширхэг давтагдаж байгаа тоотой тэнцүү. Жишээлбэл, $3 5 6 7 8 9 5 1 1 1 1 5$ блокоос $5$ цифрийг сонгох боломжийн тоо $3$ юм.

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан дөрвөн бүхэл тоон утгууд $n$, $b$, $k$ ба $x$ ($2 ≤ n ≤ 50 000, 1 ≤ b ≤ 10^{9}, 0 ≤ k < x ≤ 100, x ≥ 2$) байх ба харгалзан нэг блок дахь цифрийн тоо, блокийн тоо, $x$-д хуваагаад гарах үлдэгдэл мөн $x$ өөрөө байна.

Дараагийн мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоон утга $a_{i}$ ($1 ≤ a_{i} ≤ 9$) байх ба блок бүрт байх цифрүүдийг өгч байгаа хэрэг юм.

Гаралт

$x$ тоонд хуваагаад гарах үлдэгдэл нь $k$-тай тэнцүү байх тоог блок бүрээс яг нэг цифр авах замаар хэдэн янзаар үүсгэж авч чадах боломжийн тоог хэвлэ.

Хоёр дахь жишээн дээр боломжит бүхэл тоонууд нь $22$, $26$, $62$ ба $66$ байна. Эдгээрийн аль нь ч $2$-т хуваахад $1$ үлдэхгүй. In the second sample possible integers are $22$, $26$, $62$ and $66$. None of them gives the remainder $1$ modulo $2$.

Гурав дахь жишээн дээр боломжит бүхэл тоонууд нь $11$, $13$, $21$, $23$, $31$ ба $33$ байх ба бүгд $2$-т хуваахад $1$ үлдэнэ. Дээрх тоонуудыг гаргаж авах ганц ганц л боломж байгаа учраас нийт хариулт 6 байна.