Số Stirling loại 2 \(S(n, k)\) đếm số cách chia \(n\) phần tử phân biệt vào \(k\) tập con không rỗng (không thứ tự). Tính \(S(n, k) \bmod (10^9+7)\).

Công thức: \(S(n, k) = \frac{1}{k!} \sum_{i=0}^{k} (-1)^i \times C_k^i \times (k-i)^n\).

Định dạng đầu vào

• Một dòng chứa hai số nguyên \(n, k\) (\(1 \le k \le n \le 2000\)).

Định dạng đầu ra

• Một số nguyên là \(S(n, k) \bmod (10^9+7)\).

Ví dụ

Input:

5 2

Output:

15

Giải thích: Chia 5 phần tử vào 2 tập con khác rỗng: 15 cách.

Ràng buộc

• 100% số điểm: \(n \le 2000\).