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\)) thoả 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\).

Example

1 10

4

2 100

273

Scoring

• 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\).