Phép cộng

Bé Lan năm nay lên lớp một. Hôm nay bé được cô giáo dạy về phép cộng, tuy nhiên vì không chú ý nghe cô giảng nên bé đã không hiểu phần phép cộng có nhớ. Khi thực hiện phép cộng thập phân thông thường, nếu tổng tại một cột tạo ra phần nhớ thì phần nhớ được cộng vào cột liền kề bên trái. Bé Lan thì khác: thay vì cộng phần nhớ vào cột liền kề bên trái, bé cộng nó vào cột thứ $d$ ở bên trái, tính từ cột hiện tại.

Ví dụ, với $d=2$, phép cộng của Lan được thực hiện như sau:

  1298
+ 3812
------
 15100

Cột hàng đơn vị: $8+2=10$, viết $0$, nhớ $1$ sang cột hàng trăm. Cột hàng chục: $9+1=10$, viết $0$, nhớ $1$ sang cột hàng nghìn. Cột hàng trăm: $2+8+1=11$, viết $1$, nhớ $1$ sang cột hàng chục nghìn. Cột hàng nghìn: $1+3+1=5$. Cột hàng chục nghìn: $1$.

Là một cô bé luôn tò mò về mọi thứ, Lan hỏi bạn $q$ câu hỏi, mỗi câu hỏi là một số nguyên $n$.

Yêu cầu: Với mỗi câu hỏi, hãy đếm số cặp số nguyên dương $(a,b)$ sao cho kết quả phép cộng $a+b$ theo cách của Lan bằng $n$. Hai cặp $(a,b)$ và $(c,e)$ được xem là khác nhau nếu $a\ne c$. Vì số lượng cặp có thể rất lớn, hãy in ra phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $q$ và $d$ $(1\le q\le {10}^3;1\le d\le 7)$.
• Mỗi dòng trong $q$ dòng tiếp theo chứa một số nguyên $n$ $(1\le n\le {10}^{20})$ là một câu hỏi của Lan.

Dữ liệu ra

Gồm $q$ dòng, mỗi dòng chứa số cặp thỏa mãn của câu hỏi tương ứng, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le q\le {10}^3$, $1\le d\le 7$.
• $1\le n\le {10}^{20}$.

Subtasks

• Subtask 1 ($20\%$ số điểm): mọi số $n$ trong các câu hỏi đều không quá ${10}^3$.
• Subtask 2 ($80\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ