Nhiệm vụ của bạn là tính toán các giá trị ~a^b~ modulo ~10^9 + 7~.

Lưu ý: Giả định rằng ~0^0 = 1~.

Input

• Dòng đầu tiên là số nguyên dương ~n~ ~(1 \leq n \leq 2 \times 10^5)~ ~-~ số lượng phép tính cần thực hiện.
• ~n~ dòng tiếp theo, mỗi dòng gồm hai số nguyên không âm ~a~ và ~b~ ~(0 \leq a,b \leq 10^9)~.

Output

Gồm ~n~ dòng, mỗi dòng là kết quả của phép tính ~a^b~ modulo ~10^9 + 7~.

Sample Input

3
3 4
2 8
123 123

Sample Output

81
256
921450052

Nhiệm vụ của bạn là tính toán ~n~ hệ số nhị thức modulo ~10^9 + 7~.

Một hệ số nhị thức ~a \choose b~ có thể được tính bằng công thức ~\frac{a!}{b!(a-b)!}~. Đảm bảo rằng ~a~ và ~b~ là hai số nguyên không âm ~(0 \leq b \leq a)~.

Input

• Dòng đầu tiên là số nguyên dương ~n~ ~(1 \leq n \leq 10^5)~ ~-~ số lượng phép tính cần thực hiện.
• ~n~ dòng tiếp theo, mỗi dòng gồm hai số nguyên không âm ~a~ và ~b~ ~(0 \leq b \leq a \leq 10^6)~.

Output

Gồm ~n~ dòng, mỗi dòng là kết quả của phép tính ~a \choose b~ modulo ~10^9 + 7~.

Sample Input

3
5 3
8 1
9 5

Sample Output

10
8
126

Aquarius là một cậu bé yêu thích đọc sách. Cậu đang sở hữu một cuốn sách đặc biệt có ~n~ trang, được đánh số từ ~1~ đến ~n~.

Để tạo thêm hứng thú khi đọc, Aquarius nghĩ ra một trò chơi nhỏ: Mỗi lần đọc xong một trang mà số trang đó chia hết cho ~m~, cậu sẽ ghi lại chữ số cuối cùng của số trang đó vào sổ tay của mình. Ví dụ, nếu cuốn sách có ~15~ trang và ~m~ bằng ~5~, thì các trang chia hết cho ~5~ sẽ là ~5~, ~10~ và ~15~. Chữ số cuối cùng của các trang này lần lượt là ~5~, ~0~ và ~5~. Khi cộng các chữ số này lại, tổng mà Aquarius ghi được sẽ là ~10~.

Bây giờ, bạn hãy giúp Aquarius tính tổng các chữ số cuối cùng mà cậu ấy ghi lại được cho từng cuốn sách với nhiều bộ truy vấn khác nhau nhé!

Input

• Dòng đầu tiên là số nguyên ~Q~ ~(1 \leq Q \leq 1000)~ ~-~ số lượng truy vấn.
• ~Q~ dòng tiếp theo mỗi dòng gồm hai số nguyên dương ~n, m~ ~(1 \leq n, m \leq 10^{16})~.

Output

Gồm ~Q~ dòng, dòng thứ ~i~ trả lời đáp án cho truy vấn thứ ~i~.

Sample Input

7
1 1
10 1
100 3
1024 14
998244353 1337
123 144
1234312817382646 13

Sample Output

1
45
153
294
3359835
0
427262129093995

Nhiệm vụ của bạn là tính toán các giá trị ~a^{b^c}~ modulo ~10^9 + 7~.

Lưu ý: Giả định rằng ~0^0 = 1~.

Input

• Dòng đầu tiên là số nguyên dương ~n~ ~(1 \leq n \leq 10^5)~ ~-~ số lượng phép tính cần thực hiện.
• ~n~ dòng tiếp theo, mỗi dòng gồm ba số nguyên không âm ~a~, ~b~ và ~c~ ~(0 \leq a,b,c \leq 10^9)~.

Output

Gồm ~n~ dòng, mỗi dòng là kết quả của phép tính ~a^{b^c}~ modulo ~10^9 + 7~.

Sample Input

3
3 7 1
15 2 2
3 4 5

Sample Output

2187
50625
763327764

Mô tả

Cho ~Q~ truy vấn, mỗi truy vấn gồm hai số nguyên ~L~ và ~R~ ~(1 \leq L \leq R \leq 10^6)~. Với mỗi truy vấn, bạn cần tính tổng các số nguyên tố trong đoạn ~[L,R]~.

Input

• Dòng đầu tiên chứa một số nguyên dương ~Q~ ~(1 \leq Q \leq 10^5)~ ~-~ số lượng truy vấn.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L~ và ~R~ ~(1 \leq L \leq R \leq 10^6)~.

Output

Gồm ~Q~ dòng, mỗi dòng ứng với mỗi truy vấn, in ra một số duy nhất là tổng các số nguyên tố trong đoạn ~[L,R]~.

Ví dụ

Input

3
1 10
5 15
1 5

Output

17
36
10

Giải thích

• Truy vấn 1: Các số nguyên tố trong đoạn ~[1,10]~ là ~2, 3, 5, 7~. Tổng ~= 17~.
• Truy vấn 2: Các số nguyên tố trong đoạn ~[5,15]~ là ~5, 7, 11, 13~. Tổng ~= 36~.
• Truy vấn 3: Các số nguyên tố trong đoạn ~[1,5]~ là ~2, 3, 5~. Tổng ~= 10~.