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.

Lan thực hiện phép cộng theo một cách khác: thay vì chuyển phần nhớ sang cột liền kề bên trái, Lan chuyển nó sang 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

Cho ~q~ câu hỏi. Mỗi câu hỏi gồm một số nguyên ~n~.

Yêu cầu: Với mỗi câu hỏi, hãy đếm số lượng 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ì kết quả có thể rất lớn, hãy in kết quả lấy phần dư khi chia cho ~10^9+7~.

Input

• Dòng đầu tiên gồm 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})~.

Output

Gồm ~q~ dòng. Mỗi dòng chứa số lượng 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~.

Scoring

Sample Input 1

5 4
1897372
3782738
3289899
3289382
38298329

Sample Output 1

916606
750802
1052998
818378
7534798