Cho ~2~ số nguyên ~a~ và ~n~. Hãy tinh ~a^n~ 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 ~a~ ~(a \leq 10^9)~ và ~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 \leq 1000~.
• Sub ~2~: ~n \leq 10^{18}~.

Sample Input 1:

3 1
2 2
4 7
5 6

Sample Output 1:

4
16384
15625

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

Pikachu đang lập trình cho con máy bay điều khiển từ xa của mình. Hiện tại máy bay đang ở độ cao ~l~ và cần bay đến độ cao ~r~.

Để làm được điều này, Pikachu cần viết một chuỗi lệnh độ dài ~n~ với các lệnh:

• Bay lên một đơn vị
• Bay xuống một đơn vị
• Giữ nguyên độ cao

Biết rằng máy bay của Pikachu không thể chạm xuống đất (tức là độ cao bằng ~0~), hãy giúp cậu ấy đếm xem có bao nhiêu chuỗi lệnh thỏa mãn nhé.

Vì kết quả có thể rất lớn, hãy in ra theo module ~10^9+7~.

Input

• Gồm một dòng duy nhất chứa ~3~ số nguyên ~n~, ~l~ và ~r~.

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 10~.
• Sub ~2~: ~n \leq 20~.
• Sub ~3~: ~n \leq 1000000~.

• Sample Input 1:

3 2 1

Sample Output 1:

5

Sample Input 2:

5 1 4

Sample Output 2:

14

Sample Input 3:

3 1 5

Sample Output 3:

0