Cho 2 số tự nhiên ~ k,n ~. Tính ~ C^{k}_{n} ~ . Vì kết quả rất lớn nên ta chỉ lấy số dư khi chia cho ~ 10^9 +7 ~.

Input

2 sô tự nhiên k,n trên cùng 1 dòng (~ 1 \le k \le n \le 1000 ~).

Output

In ra kết quả theo yêu cầu bài toán

Sample

Input #1

3 6

Output #1

20

Cho 2 số tự nhiên ~ k,n ~. Tính ~ C^{k}_{n} ~ . Vì kết quả rất lớn nên ta chỉ lấy số dư khi chia cho ~ 10^9 +7 ~.

Input

2 sô tự nhiên k,n trên cùng 1 dòng (~ 1 \le k \le n \le 1000000 ~).

Output

In ra kết quả theo yêu cầu bài toán

Sample

Input #1

3 6

Output #1

20

Cho 3 số  ~ k,n,m ~  .Tính  số dư của ~C^{k}_{n} ~  khi chia cho ~m~ .

Input

Duy nhất 1 dòng chứ 3 số nguyên theo thứ tự ~ k ,n ,m ~ (~ 0 < k \le 10^6 ~ , ~ 1 \le n \le 10^9 ~ , ~ 1 \le m \le 10^9 ~ , ~ k \le n ~ ).

Output

In ra kết quả theo yêu cầu bài toán

Sample

Input #1

2 3 100

Output #1

3

• Cho số tự nhiên n và số nguyên tố p. Hỏi có bao nhiêu cặp số (j,i) thỏa mãn điều kiện 0 ~\le~ j ~\le~ i < n mà ~C_i^j~ chia hết cho p?

Input

• Gồm một dòng duy nhất chứa hai số nguyên n và p, n < 3 * ~10^6~, p < 100

Output

• In ra kết quả của bài toán

Sample

Input #1

5 3

Output #1

3