Cho hai số nguyên dương ~a~, ~n~. Tính ~a^n~.

Input

Gồm một dòng chứa hai số nguyên dương ~a~, ~n~. (~a, n \leq 20~)

Dữ liệu đảm bảo ~a^n~ luôn nhỏ hơn ~10^{19}~.

Output

In ra giá trị ~a^n~.

Sample Test

Input:

2 3

Output:

8

Cho số nguyên dương ~N~. Hãy đếm xem có bao nhiêu số nguyên nằm trong đoạn ~(N - 1)/2~ (phép chia lấy phần nguyên) đến ~N^2~.

Input

Gồm một số nguyên dương ~N~. (~1 \le N \le 1000~)

Output

In ra số lượng số nguyên thỏa mãn điều kiện đã cho.

Sample Test

Input:

4

Output:

16

Giải thích:

• ~(N - 1)/2 = (4 - 1)/2 = 1~ (dư 1)
• ~N^2 = 4^2 = 16~

~\rightarrow~ Có tất cả ~16~ số hạng không bé hơn ~1~ và không lớn hơn ~16~.

Để chào đón sự trở về của các anh hùng Đội tuyển quốc gia Việt Nam, thtb8 muốn phamgiaminh trả lời ~T~ bài toán, bài toán thứ ~i~ gồm hai số nguyên dương ~l_i~ và ~r_i~. Gọi tập các số nguyên tố nằm trong khoảng giữa ~l_i~ và ~r_i~ được sắp xếp theo thứ tự tăng dần là

~S =~ {~p_1,p_2,...,p_k~}. thtb8 cần phamgiaminh tính công thức sau:

Vì kết quả có thể rất lớn nên thtb8 muốn phamgiaminh trả lời các kết quả là phần dư khi chia cho ~10^9+7~. phamgiaminh khá buồn vì Park Hang Seo chia tay VN nên muốn nhờ các bạn giúp phamgiaminh trả lời các bài toán đó.

Dữ liệu

• Dòng đầu tiên ghi một số nguyên dương ~T~ là số lượng bài toán.

• Dòng thứ ~i~ trong ~T~ dòng tiếp theo gồm ~2~ số nguyên dương ~l_i~ và ~r_i~.

• ~l_i,r_i, T ≤ 10^6~

Kết quả

• In ra ~T~ dòng, dòng thứ ~i~ là kết quả của bài toán thứ ~i~.

Sample

Input

2
1 5
3 7

Output

23
34