Trọng số của một số tự nhiên ~x~ được tính bằng cách biểu diễn ~x~ dưới dạng hệ cơ số 10 và tính tổng tất cả các số sinh ra từ các đoạn con của ~x~.
Ví dụ trọng số của 10034 là ~1+10+100+1003+10034+0+00+003+0034+0+03+034+3+34+4=11263~.

Hoài đang nghiên cứu các tính chất đặc biệt của số. Có liệt kê tất cả các số nguyên dương có ~n~ chữ số, các chữ số đều bé hơn hoặc bằng ~7~ và không có số ~0~ đứng đầu. Cô muốn biết trong các số vừa liệt kê, có bao nhiêu bộ ba số (~x, y, z~) thỏa mãn ~x < y < z~ và tổng trọng số của ~x, y, z~ chia hết cho ~k~.

Input

Gồm hai số nguyên dương ~n, k~.

Output

Ghi một số nguyên duy nhất là số bộ ba tìm được, chỉ cần in ra kết quả sau khi chia lấy dư cho ~10^9+7~.

Subtasks

• Có 8% test với ~n \le 6~, ~k \le 10~;
• Có 20% test với ~n \le 9~, ~k \le 100~;
• Có 28% test với ~n \le 100~, ~k \le 100~;
• Có 44% test với ~n \le 1000~, ~k \le 1000~.

Sample Input 1

1 10

Sample Output 1

4

Sample Input 2

2 100

Sample Output 2

273

Sample Input 3

8 10

Sample Output 3

51145857