Hãy đếm số hoán vị độ dài ~n~ sao cho: ~a[i] \neq i~, ~\forall 1 \leq i \leq n~. Vì kết quả có thể rất lớn, hãy in ra kết quả lấy phần dư cho ~10^9+7~.

Input

Dòng ~1~: Ghi số nguyên dương ~n~ ~(n≤10^6)~.

Output

Dòng ~1~: Chứa kết quả của bài toán.

Scoring

Sample Input 1

2

Sample Output 1

1

Hãy đếm số cặp ~(i, j)~ nguyên tố cùng nhau, sao cho ~1 ≤ i ≤ n~ và ~1 ≤ j ≤ m~. Hai số nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng ~1~.

Input

Dòng ~1~: Ghi ~2~ số nguyên dương ~n, m~ ~(n, m≤10^7)~.

Output

Dòng ~1~: Chứa kết quả của bài toán.

Scoring

Sample Input 1

3 4

Sample Output 1

9

Có ~n~ viên sỏi được đánh số từ ~1~ đến ~n~. Hãy đếm số cách chọn ra ~k~ viên sỏi trong ~n~ viên sỏi đó, vì số cách có thể rất lớn nên hãy in ra kết quả theo module ~10^9 + 7~.

Input

• Dòng một chứa hai số nguyên dương ~t \; (t \leq 1000)~ và ~s~ lần lượt là số bộ dữ liệu của test và subtask của test.
• ~t~ dòng sau, mỗi dòng chứa ~2~ số nguyên dương ~n~ và ~k~ ~(k \leq n)~ tương ứng với ~1~ bộ dữ liệu.

Output

• Gồm ~t~ dòng, mỗi dòng chứa kết quả của một test theo thứ tự đầu vào.

Subtask

• Sub ~1~: ~n, k \leq 1000~.
• Sub ~2~: ~n \leq 10^9, \; k \leq 10^3~.
• Sub ~3~: ~n, k \leq 10^6~.

Sample Input 1:

3 1
1 1
3 2
9 5

Sample Output 1:

1
3 
126

Pikachu đang ở ô ~(0,0)~ và cậu ấy muốn đi đến ô ~(n, m)~. Biết rằng khi đang ở ô ~(x,y)~, Pikachu chỉ có thể đi đến ô ~(x + 1, y)~ hoặc ~(x, y + 1)~. Hãy đếm số cách mà Pikachu có thể đi, vì kết quả có thể rất lớn nên hãy in ra theo module ~10^9+7~.

Input

• Dòng một chứa hai số nguyên dương ~t \; (t \leq 1000)~ và ~s~ lần lượt là số bộ dữ liệu của test và subtask của test.
• ~t~ dòng sau, mỗi dòng chứa ~2~ số nguyên dương ~n~ và ~m~ tương ứng với ~1~ bộ dữ liệu.

Output

• Gồm ~t~ dòng, mỗi dòng chứa kết quả của một test theo thứ tự đầu vào.

Subtask

• Sub ~1~: ~n, m \leq 1000~.
• Sub ~2~: ~n, m \leq 10^6~.

Sample Input 1:

3 1
2 2
4 7
5 6

Sample Output 1:

6
330
462

Bài này giống bài trước nhưng Pikachu có thẻ đi chéo

Pikachu đang ở ô ~(0,0)~ và cậu ấy muốn đi đến ô ~(n, m)~. Biết rằng khi đang ở ô ~(x,y)~, Pikachu chỉ có thể đi đến ô ~(x + 1, y)~, ~(x, y + 1)~ hoặc ~(x + 1, y + 1)~. Hãy đếm số cách mà Pikachu có thể đi, vì kết quả có thể rất lớn nên hãy in ra theo module ~10^9+7~.

Input

• Gồm một dòng duy nhất chứa ~2~ số nguyên dương ~n~ và ~m~.

Output

• Gồm một dòng chứa kết quả bài toán.

Subtask

• Sub ~1~: ~n, m \leq 1000~.
• Sub ~2~: ~n, m \leq 10^6~.

Sample Input 1:

4 3

Sample Output 1:

129

Pikachu có ~n~ viên sỏi, mỗi viên một màu khác nhau và cậu ấy muốn xếp một tòa tháp bằng toàn bộ đống sỏi đấy. Cách xây tháp của Pikachu là xây lần lượt từng tầng một, mỗi tầng có không quá ~k~ viên sỏi, tầng trên có thể có nhiều sỏi hơn tầng dưới nhưng mỗi tầng phải có ít nhất một viên sỏi.

Bây giờ, cậu ấy muốn biết có bao nhiêu cách xây khác nhau, hai cách xây khác nhau khi thõa mãn một trong các điều kiện sau:

• Hai tòa tháp có số tầng khác nhau.
• Tồn tại ít nhất một tầng mà số sỏi của hai tòa tháp khác nhau.
• Trong cùng một tầng, màu của các viên sỏi trong hai tòa tháp khác nhau. Vì số cách có thể rất lớn, hãy đưa ra kết quả theo module ~10^9~.

Input

• Gồm một dòng duy nhất chứa hai số nguyên dương ~n~ và ~k~ ~(k \leq n)~.

Output

• Gồm một dòng duy nhất chứa kết quả của bài toán.

Subtask

• Sub ~1~: ~n \leq 8~.
• Sub ~2~: ~n \leq 50~.
• Sub ~3~: ~n \leq 300~.

Sample Input 1:

3 2

Sample Output 1:

12

Một chiếc máy bay đang ở độ cao ~h1~. Phi công cần điều khiển để máy bay đạt độ cao ~h2~ trong đúng ~n~ giây.

Tại mỗi giây, phi công có thể điều khiển bởi một trong ba lệnh: Tăng độ cao lên ~1~, giảm độ cao đi ~1~, giữ nguyên độ cao.

Hãy đếm số cách điều khiển khác nhau. Biết rằng máy bay có thể chạm vào mặt đất (độ cao ~0~) nhưng không thể đạt độ cao âm. Hai cách điều khiển được cho là khác nhau nếu tồn tại ~i~, ~1 ≤ i ≤ n~ sao cho lệnh điều khiển ở thời điểm thứ ~i~ trong hai cách trên là khác nhau.

Input

Dòng ~1~: Ghi ~3~ số nguyên dương ~h1, h2, n~ ~(h1, h2, n≤10^5)~.

Output

Dòng ~1~: Chứa kết quả của bài toán lấy dư cho ~10^9 + 7~.

Scoring

Sample Input 1

0 0 6

Sample Output 1

51