Cho một bảng vuông ~n \times n~ ô, một số ô có thể có bẫy. Các ô được đánh thứ tự trên trên xuống dưới, từ trái sang phải.

Nhiệm vụ của bạn là tính số lượng cách đi từ ô trái trên (toạ độ ~(1, 1)~) đến ô phải dưới (toạ độ ~(n, n)~) mà không đi qua bẫy. Bạn chỉ có thể di chuyển sang phải hoặc xuống dưới.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ - kích thước bảng (~n \leq 1000~).
• ~n~ dòng tiếp theo, mỗi dòng chứa ~n~ kí tự mô tả bảng vuông:
  • . mô tả một ô trống (có thể đi qua);
  • * mô tả một ô có bẫy (không thể đi qua).

Output

• In ra số lượng đường đi, lấy phần dư khi chia cho ~10^9 + 7~.

Sample Test

Nhiệm vụ của bạn là tìm dãy con tăng dài nhất trong mảng ~n~ phần tử.

Dãy con là dãy nhận được khi xóa một hay nhiều phần tử từ mảng ban đầu và giữ nguyên thứ tự các phần tử còn lại.

Input

• Dòng thứ nhất chứa số nguyên ~n \ (1 \leq n \leq 5000)~: số phần tử trong mảng
• Dòng thứ hai chưa ~n~ số nguyên ~x_1, x_2,..., x_n \ (1 \leq x_i \leq 10^9)~: các phần tử của mảng

Output

• In ra độ dài dãy con tăng dài nhất.

Sample Test

Leo cầu thang

Một người muốn leo lên một cầu thang có n bậc.

Mỗi bước, người đó có thể bước lên 1, 2 hoặc 3 bậc. Tuy nhiên, để tránh bị mỏi chân do lặp lại cùng một kiểu bước quá nhiều lần, người đó không được bước cùng một số bậc trong ba lần liên tiếp.

Nói cách khác, trong dãy các bước đi, không được xuất hiện ba số liên tiếp bằng nhau.

Hãy đếm số cách leo hết cầu thang.

Vì kết quả có thể rất lớn, hãy in ra phần dư của kết quả khi chia cho ~998244353~.

Input

Gồm một dòng duy nhất chứa số nguyên ~n~.

Output

In ra một số nguyên duy nhất là số cách leo hết cầu thang, lấy modulo ~998244353~.

Giới hạn

~1 \le n \le 10^5~

Sample Test

Cho dãy số nguyên dương ~a_1,a_2,...,a_n~ và một số ~k~.

Một tập con ~S~ của ~\{1,2,...,n\}~ được gọi là tập ~xor~ nếu ~S~ không có quá ~k~ phần tử và với mọi ~i,j~ thuộc ~S~ ta có ~a_i + a_j = a_i \oplus a_j~, với ~\oplus~ là phép ~xor~.

Trọng số của ~S~ được hiểu là ~\sum a_i, \forall i \in S~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai chứa số nguyên dương ~k~.
• Nếu ~n \le 10^4~ thì có dòng thứ ba, ngược lại không có.

Output

• Ghi ra tổng trọng số tất cả các tập ~xor~, sau khi lấy dư cho ~10^9+7~.

Subtask

• Sub ~1~ ~(20\%)~: ~1 \le n,k,a_i \le 10^2~
• Sub ~2~ ~(20\%)~: ~1 \le n,k,a_i \le 10^3~.
• Sub ~3~ ~(20\%)~: ~1 \le n,k \le 10^4~ và ~a_i = i~.
• Sub ~4~ ~(20\%)~: ~1 \le n,k,a_i \le 10^4~.
• Sub ~5~ ~(20\%)~: ~1 \le n,k \le 10^{1000}~ và ~a_i = i~.

Sample Input 1

6 
3
1 1 2 3 4 5

Sample Output 1

66

Cho hai số nguyên dương n và x, trong đó x là một số nguyên tố. Hãy tìm số nguyên không âm lớn nhất k sao cho x^k là ước của n!.

Nói cách khác, cần tìm k lớn nhất thỏa mãn: ~x^k~ là ước của ~n! = 1\times 2\times \ldots \times n~.

Input

Dòng đầu tiên chứa số nguyên T là số bộ test.

Mỗi trong T dòng tiếp theo chứa hai số nguyên n và x.

Output

Với mỗi test, in ra số nguyên lớn nhất k cần tìm trên một dòng.

Giới hạn

~1 \le T \le 10^5~

~1 \le n \le 10^{18}~

~2 \le x \le 10^{12}~

x là số nguyên tố.

Ví dụ

Để chào mừng Kỷ niệm 50 năm Thành phố mang tên Bác, Ban tổ chức sự kiện muốn chọn ra ~k~ khối đại biểu thanh niên tiêu biểu để trao cờ luân lưu danh dự trong lễ đài chính.

Đội hình đang có tất cả ~n~ khối đại biểu được xếp thành một hàng dọc chờ tiến vào khán đài, được đánh số lần lượt từ vị trí thứ ~1~ đến ~n~. Để đảm bảo đội hình trao cờ trông đẹp mắt, trải đều và không bị dồn ứ trên sân, Ban tổ chức đề ra các quy tắc như sau:

• Trong ~n~ khối thì chỉ trao đúng ~k~ lá cờ cho ~k~ khối (mỗi khối chỉ nhận tối đa một lá cờ);
• Khối thứ ~i~ đã được chọn nhận cờ thì hai khối kế bên (trước và sau) là khối thứ ~i - 1~ và khối thứ ~i + 1~ sẽ không được nhận cờ nữa ~(i = 2, 3, …, n - 1)~.
• Khối thứ ~1~ đã nhận cờ thì khối thứ ~2~ không được nhận. Tương tự, nếu khối thứ ~n~ được nhận cờ thì khối thứ ~n - 1~ chắc chắn sẽ không được nhận cờ.

Với các quy tắc như trên, Ban tổ chức muốn biết có bao nhiêu cách để chọn các khối trao cờ? Hãy viết chương trình giúp Ban tổ chức trả lời bài toán này.

Yêu cầu. Cho hai số nguyên dương ~n~ và ~k \ (k < n \leq 10^5)~. Hãy xác định số cách chọn trao cờ, chia lấy phần dư cho ~m \ (2 \leq m \leq 10^9)~

Input

Gồm một dòng chứa ~3~ số nguyên dương ~n,k,m~.

Output

Gồm một số nguyên là kết quả tìm được.

Sample Input

6 3 12345

Sample Output

4

Subtasks

• Subtask 1 (20% số điểm). ~n \leq 20~.
• Subtask 2 (80% số điểm). Không có ràng buộc gì thêm.