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 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ả vấn đề

Viết chương trình nhập 2 số nguyên dương, tìm ước số chung lớn nhất (gcd - greatest common divisor) và bội số chung nhỏ nhất (lcm - least common multiple)  của chúng.

Input

Nhập 2 số nguyên dương a và b (1 ≤ a, b ≤ 10~^5~)

Output

In ra ước chung lớn nhất và bội chung nhỏ nhất

Sample Input 1

2 4

Sample Output 1

2 4

Bạn được cung cấp một mảng gồm ~n~ số nguyên. Bạn có quyền lựa chọn loại bỏ một phần tử bất kỳ từ mảng hoặc không loại bỏ bất kỳ phần tử nào. Nhiệm vụ của bạn là xác định ước số chung lớn nhất ~gcd~ của các phần tử còn lại trong mảng sau khi thực hiện lựa chọn đó. Hãy tìm giá trị ~gcd~ lớn nhất mà bạn có thể thu được từ dãy số đã cho sau khi loại bỏ tối đa một phần tử.

Input

• Dòng đầu tiên gồm số nguyên ~n~ ~(2 \le n \le 10^5)~ - số lượng phần tử của mảng.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1,a_2,...,a_n~ ~(1 \le a_i \le 10^7)~ - giá trị của phần tử thứ ~i~.

Output

• In ra một số nguyên duy nhất là ~gcd~ lớn nhất của dãy.

Sample Input 1

5
2 3 4 6 8

Sample Output 1

2

Cho số nguyên dương ~m,n~. Hãy đếm xem có bao nhiêu cặp số nguyên dương ~x,y~ có thứ tự sao cho bội chung nhỏ nhất của chúng đúng bằng ~m~ còn ước chung lớn nhất của chúng thì chia hết cho ~n~.

Input

Một dòng duy nhất gồm các số nguyên dương ~m,n~ với ~1 \le n \le m \le 10^9.~

Output

Đáp số của bài toán.

Sample input

12 2

Sample output 1

9

Giải thích

Trong VD đã cho, ta cần đếm cặp số ~x,y~ có ~lcm = 12~ và ~gcd~ chia hết cho ~2~. Ta liệt kê được các cặp số sau: ~(2,12),(12,2),(4,6),(6,4),(4,12),(12,4),(6,12),(12,6),(12,12).~

Nhiệm vụ của bạn là tính ~m~ tổ hợp ~C_n^k~ theo modulo ~10^9 + 7~.

Tổ hợp ~C_n^k~ có thể tính theo công thức. ~C_n^k = \frac{n!}{(n - k)!k!}~.

Input

• Dòng đầu tiền gồm số ~m~.

• ~m~ dòng tiếp theo. Mỗi dòng gồm 2 số ~n~, ~k~.

Output

• Gồm ~m~ dòng. Mỗi dòng là kết quả của ~C_n^k~ theo modulo ~10^9 + 7~.

Giới hạn

• ~1 \le m \le 10^5~

• ~0 \le k \le n \le 10^6~

Example

Input

3
5 3
8 1
9 5

Output

10
8
126

Nhận thấy các con của mình rất chăm học thuật toán nên bố Tài SC (super cute) đã ra cho chúng một bài toán ngây thơ như sau: cho ~q~ số nguyên dương (không nhất thiết phân biệt), hãy tính tổng ước của từng số. Các con cảm thấy rất giận dỗi vì lại ra một bài căn bản như thế, cho đến khi chúng đọc được kỹ các subtask, hãy làm thử bài toán này của bố Tài nhé.

Input

Dòng đầu tiên là số nguyên dương ~q~.

Dòng tiếp theo là ~q~ số nguyên dương ~a_1, a_2, ..., a_q.~

Output

In ra ~q~ số là đáp số của bài toán.

Sample input

4
2 4 10 9

Sample output

3 7 18 13

Subtasks

• Subtask 1 (15% số điểm): ~q ≤ 10^4; a_i ≤ 10^3~ với ~(1 ≤ i ≤ q)~
• Subtask 2 (25% số điểm): ~q ≤ 10^5; a_i ≤ 10^5~ với ~(1 ≤ i ≤ q)~
• Subtask 3 (35% số điểm): ~q ≤ 10^5; a_i ≤ 10^6~ với ~(1 ≤ i ≤ q)~
• Subtask 4 (25% số điểm): ~q ≤ 10^6; a_i ≤ 10^{12}~ và ~a_{i+1} = a_i + 1~ với ~1 ≤ i <q.~</li>

Số nguyên tố, gạch xây toán học
Ước số chúng, đếm đếm tỉ mỉ
Hai, ba, năm - những viên gạch nhỏ
Xếp chồng lên nhau, tạo nên kỳ tích
Phân tích số, tìm ra yếu tố
Đếm từng ước, nguyên tố hiện hình
Thuật toán chạy, con số hiển lộ
Bí ẩn toán học, dần dần sáng tỏ

Có một số nguyên dương ~n~ mang theo nhiều bí ẩn. Các số từ 1 đến ~n~ không chỉ đóng vai trò là ước của ~n~, mà một số trong đó còn là những số nguyên tố đặc biệt. Nhiệm vụ của bạn là tìm ra bao nhiêu số trong đoạn từ 1 đến ~n~ vừa là ước của ~n~, vừa là số nguyên tố.

Giới hạn

• ~1 ≤ n ≤ 10^6~

Đầu vào

• Dòng đầu tiên: số nguyên ~n~

Đầu ra

• Một số nguyên duy nhất: số lượng các ước nguyên tố của ~n~

Sample Input

12

Sample Output

2

Mô tả

...
Nếu những tiếc nuối nay không còn
Thì có chăng bây giờ mình mới có được nhau
Có lẽ chuyện tình đôi chúng mình
Tình cờ như vô hình từ bao lần gặp gỡ
Nếu những kí ức kia quay về
Thì chắc anh sẽ buồn vì đôi mắt của em
Có lẽ phút giây gặp nhau
Giống như mùa thu đang đợi cơn gió đông sang vụt qua
...

Đó là những giai điệu vô cùng suy tư trong bài hát Nếu những tiếc nuối của Vũ được ra mắt trong thời gian gần đây. Vì bài hát quá hay nên cậu bé Kluco đã nghe đi nghe lại rất nhiều lần. Thậm chí, trong lúc làm bài tập trên IUHCoder, cậu bé cũng nghe bài hát này đến nỗi quên luôn cách giải một bài toán vô cùng đơn giản. Bài toán ấy có nội dung như sau: Cho hai số nguyên ~a~ và ~b~, hãy tính tích của chúng rồi in ra kết quả. Vì kết quả có thể rất lớn nên hãy in kết quả sau khi đã modulo ~10^9 + 7~.

Vì Kluco đã quên cách giải nên bạn hãy giúp anh ấy nhé!

Input

Một dòng duy nhất chứa hai số nguyên ~a, b~ ~(-10^{18} \leq a, b \leq 10^{18})~.

Output

Một dòng duy nhất là đáp án của bài toán.

Ví dụ

Input

2 3

Output

6

Lão Hạt, một tên trộm xảo quyệt từ xứ Dừa, trong một phi vụ trộm cắp tình cờ nhặt được chiếc đèn thần cổ. Tò mò, hắn xoa vào chiếc đèn, khiến thần đèn xuất hiện trong làn khói mờ ảo. Thần đèn hứa sẽ ban cho Lão Hạt ba điều ước, nhưng với điều kiện hắn phải chứng minh sự thông minh vượt trội.

Thần đèn đưa ra một bài toán:

"Ta sẽ cho ngươi dãy số nguyên ~n~ phần tử, phần tử thứ ~i~ có giá trị là ~a_i~, ngươi sẽ nhận được ba điều ước nếu người tìm được số có ba ước".

Lão Hạt, vốn tinh ranh, nhưng trước thử thách của thần đèn, liệu có đủ thông minh để giải bài toán và đạt được điều ước mà hắn mong muốn hay không? Vì quá tò mò nên bạn đã thử đếm số lượng số trong mảng có đúng ba ước.

Input

• Dòng đầu tiên gồm số nguyên ~n~ ~(1 \le n \le 10^3)~ - số lượng phần tử của mảng.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2,...a_n~ ~(1 \le a_i \le 10^3)~ - giá trị của phần tử thứ ~i~.

Output

• Gồm một số nguyên duy nhất là số lượng số trong mảng có đúng ba ước số.

Sample Input

5
1 3 4 9 25

Sample Output

3

Note

• Đây là Lão Hạt chứ không phải Lão Hạc.