Đếm số có đúng k chữ số khác 0

Đề bài

Cho hai số nguyên dương \(n\) và \(k\).

Hãy đếm số lượng số nguyên dương có đúng \(n\) chữ số sao cho số đó có chính xác \(k\) chữ số khác \(0\).

Một số được coi là hợp lệ nếu đồng thời thỏa mãn:

• Số đó có đúng \(n\) chữ số.
• Chữ số đầu tiên khác \(0\).
• Trong \(n\) chữ số của số đó có đúng \(k\) chữ số khác \(0\).

Vì kết quả có thể rất lớn, hãy in kết quả theo modulo \(1000000007\).

Input

Một dòng duy nhất chứa hai số nguyên dương \(n\) và \(k\).

Output

In ra một số nguyên duy nhất là số lượng số thỏa mãn yêu cầu.

Kết quả được lấy modulo \(1000000007\).

Ràng buộc

• Subtask 1 (20% số điểm): \(1 \le n \le 6\).
• Subtask 2 (30% số điểm): \(1 \le n \le 10^5\).
• Subtask 3 (50% số điểm): \(1 \le n \le 10^9,\ 1 \le k \le \min(n,10)\).

Ví dụ 1

Input:

4 1

Output:

9

Ví dụ 2

Input:

4 2

Output:

243

Ví dụ 3

Input:

5 3

Output:

4374