Bài tập

Những ngọn nến lung linh huyền ảo khiến biết bao người đam mê, trong số đó có Nhan_Tai. Một hôm, Tai_Nhan đưa cho anh \(n\) cây nến với độ cao đôi một khác nhau. Theo đó, Nhan_Tai sẽ phải xếp \(n\) cây nến này theo một đường thẳng sao cho các cây nến ở vị trí chẵn thì cao hơn hai cây nến hai bên (nếu có), và dĩ nhiên, các cây nến ở vị trí lẻ thì thấp hơp hai cây nến hai bên (nếu có). Cụ thể, cách xếp phải thỏa mãn với mọi \(1 ≤ i ≤ n\):

• Nếu \(i\) chẵn: \(i > 1\) ⇒ \(h_{i−1} < h_{i}\); \(i < n\) ⇒ \(h_{i+1} < h_{i}\)

• Nếu \(i\) lẻ: \(i > 1\) ⇒ \(h_{i−1} > h_{i}\) ; \(i < n\) ⇒ \(h_{i+1} > h_{i}\)

Ở đây \(h_{i}\) được hiểu như là độ cao của cây nến xếp ở vị trí thứ \(i\) trên đường thẳng. Anh ta muốn biết mình có bao nhiêu cách khác nhau để xếp các cây nến. Vốn nhìn xa trông rộng, Nhan_Tai biết sẽ có thể có rất nhiều cách xếp, anh ta chỉ yêu cầu in ra \(9\) chữ số tận cùng của số cách xếp

Input

• Dòng đầu chứa \(2\) số nguyên \(Q\) là số lượng testcase

• Mỗi testcase nằm trên một dòng chứa đúng một số nguyên dương: \(n\)

Output

Gồm \(Q\) dòng trả lời cho \(Q\) testcase

Example

5
6
7
8
9
10

000000061
000000272
000001385
000007936
000050521

Scoring

• \(N, Q ≤ 5000\)

• Có \(50\%\) số test với \(n ≤ 100\)

Xét dãy vô hạn các số tự nhiên liên tiếp bắt đầu từ \(1\): \(1, 2, 3,...\) và \(n\) số nguyên dương \(a_{1}, a_{2}, ..., a_{n}\). Trên dãy vô hạn các số tự nhiên này, tiến hành xóa hết các số chia hết cho \(a_{1}\), sau đó xóa hết các số chia hết cho \(a_{2}\) mà chưa được xóa,..., cuối cùng xóa hết các số chia hết cho \(a_{n}\) mà chưa được xóa. Đánh số các số chưa được xóa bắt đầu từ \(1\), người ta muốn biết số được đánh số thứ \(k\) là số nào?

Yêu cầu: Cho dãy số \(a_{1}, a_{2}, ..., a_{n}\) và \(k\), hãy tìm số tự nhiên được đánh số thứ \(k\) trên dãy sau khi xóa.

Input

--- Dòng đầu chứa số nguyên \(T\) là số bộ dữ liệu;

--- \(T\) nhóm dòng sau, mỗi nhóm có dạng:

o Dòng đầu của nhóm chứa hai số nguyên dương \(n\) và \(k\) \((1 ≤ k ≤ 10^{15})\);

o Dòng thứ hai của nhóm chứa \(n\) số nguyên dương \(a_{1}, a_{2}, ..., a_{n}\) \((1 < a_{i} ≤ 10^{15})\).

Output

• Gồm \(T\) dòng, mỗi dòng chứa một số tự nhiên là kết quả tương ứng của bộ test trong dữ liệu vào.

Example

1
2 5
3 4

10

Scoring

\(30\%\) số test có \(n = 1\)

\(30\%\) số test có \(n = 2\)

\(40\%\) số test có \(n \leq 10\)

Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(A_1,A_2,…,A_n\). Hãy loại một phần tử bất kỳ trong dãy số và đặt \(P\) tích các số còn lại. Phân tích thừa số nguyên tố của \(P\), sau đó tính tổng các số mũ trong thừa số nguyên tố đó. Hãy tìm cách bỏ loại bỏ số nào để tổng các số mũ nhỏ nhất có thể.

Ví dụ: cho dãy số gồm \(4\) số \(1; 2; 4; 10\). có 2 cách bỏ đều cho tổng số mũ bằng \(3\) là nhỏ nhất:

• Cách 1: Loại bỏ số \(4\), ta có \(P=1 * 2*10=20=2^2*5\) có tổng số mũ bẳng \(3\)

• Cách 2: Loại bỏ số \(10,\) ta có \(P=1 * 2*4=8=2^3\) có tổng số mũ bẳng \(3\)

Yêu cầu: Cho dãy số \(A\), hãy in ra tổng số mũ nhỏ nhất của phân tích thừa số sau khi bỏ một phần tử.

Input

• Dòng đầu tiên chứa dãy số \(n (n≤10^5)\).

• Dòng thứ 2 chứa \(n\) phần tử của dãy số \(A (A_i≤10^6)\).

Output

Một số nguyên là tổng số mũ nhỏ nhất của phân tích thừa số sau khi bỏ một phần tử.

Example

4
1 2 4 10

3

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N≤10^4\) và \(A_i≤3\).

• Subtask \(2\) (\(30\%\) số điểm): \(N≤10^4\) và \(A_i≤8\).

• Subtask \(3\) (\(30\%\) số điểm): \(N≤10^4\) và \(A_i≤10^6\).

• Subtask \(4\) (\(10\%\) số điểm): trường hợp còn lại.

Có \(n\) thành phố và \(m\) chuyến bay kết nối giữa chúng. Bạn muốn đi từ Syrjälä đến Lehmälä để bạn đến thăm mỗi thành phố đúng một lần. Có bao nhiêu tuyến đường khả thi?

Input

• Dòng đầu tiên là hai số nguyên \(n\) và \(m\): số thành phố và chuyến bay. Các thành phố được đánh số \(1,2,\ldots, n\). Thành phố \(1\) là Syrjälä, và thành phố \(n\) là Lehmälä.

• Sau đó, có \(m\) dòng mô tả các chuyến bay. Mỗi dòng gồm hai số nguyên \(a\) và \(b\): có một chuyến bay từ thành phố \(a\) đến thành phố \(b\). Tất cả các chuyến bay đều là chuyến bay một chiều.

Output

• In ra một số nguyên: số tuyến đường theo modulo \(10^9 + 7\).

Example

4 6
1 2
1 3
2 3
3 2
2 4
3 4

2