Số điện thoại tốt

Một số điện thoại có đúng $n$ chữ số (chữ số đầu tiên có thể là $0$).

Cho số nguyên $k$ là ước của $n$. Chia số điện thoại thành $n/k$ khối liên tiếp, mỗi khối gồm $k$ chữ số: khối thứ nhất gồm các vị trí $1,2,\dots ,k$, khối thứ hai gồm các vị trí $k+1,k+2,\dots ,2k$, và cứ như vậy.

Mỗi khối $c_1{c}_2\dots c_k$ được xem là một số nguyên có giá trị $c_1·{10}^{k-1}+c_2·{10}^{k-2}+\dots +c_k$ (khối có thể bắt đầu bằng chữ số $0$, khi đó giá trị của nó nhỏ hơn ${10}^{k-1}$).

Cho hai dãy $a_1,a_2,\dots ,a_{n/k}$ và $b_1,b_2,\dots ,b_{n/k}$. Một số điện thoại được gọi là tốt nếu với mọi $i$, khối thứ $i$ đồng thời thoả mãn:

• Chữ số đầu tiên của khối thứ $i$ khác $b_i$;
• Giá trị của khối thứ $i$ chia hết cho $a_i$.

Hãy đếm số lượng số điện thoại tốt có độ dài $n$, kết quả lấy phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$.
• Dòng thứ hai chứa $n/k$ số nguyên $a_1,a_2,\dots ,a_{n/k}$.
• Dòng thứ ba chứa $n/k$ số nguyên $b_1,b_2,\dots ,b_{n/k}$.

Dữ liệu ra

Một số nguyên duy nhất: số lượng số điện thoại tốt độ dài $n$, lấy modulo ${10}^9+7$.

Ràng buộc

• $1\le n\le 100000$
• $1\le k\le min(n,9)$, và $n$ chia hết cho $k$
• $1\le a_i<{10}^k$
• $0\le b_i\le 9$

Ví dụ