Gần đây ~Mingle~ mới học xong về số chính phương và cậu tỏ ra vô cùng thích thú với những bài toán về số chính phương. Với một số nguyên ~k~, ~Mingle~ thắc mắc không biết rằng có tổng cộng bao nhiêu cách để biểu diễn ~k~ dưới dạng tổng bình phương của không quá hai số nguyên dương. Câu hỏi này khiến ~Mingle~ luôn chìm trong suy tư, đêm quên ăn, ngày quên ngủ.

Các bạn hãy giúp ~Mingle~ giải bài toán này để cậu sớm quay lại cuộc sống bình thường nhé.

Ví dụ :

• Với ~k = 1~ thì kết quả sẽ là ~1~ .

• Với ~k = 25~ thì kết quả sẽ là ~3~. Cụ thể là:

  • ~25 = 5^2~.

  • ~25 = 3^2 + 4^2~

  • ~25 = 4^2 + 3^2~

Input

• Một dòng duy nhất gồm số tự nhiên ~k~ (~1 \le k \le 10^{12}~).

Output

• Một dòng gồm đáp án của bài toán.

Subtask

• ~30\%~ số test thỏa mãn ~1 \le k \le 10^{6}~.

• ~70\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

25

Sample Output 1

3

Bé Quân đang học toán, cô giáo cho bé bài toán tính giá trị một số biểu thức chỉ gồm các số và ~3~ loại phép tính:

• Cộng

• Trừ

• Nhân

Quân đã tính ra ngay được đáp án, nhưng bài để nộp cho cô nên bé nhờ bạn kiểm tra lại đáp án của bé xem có đúng không.

Yêu cầu: Bạn hãy tính giá trị của biểu thức để cho bé Quân so sánh nhé.

Input

• Dòng đầu chứa số nguyên dương ~T~ ~(1 \le T \le 10)~ là số biểu thức bé Quân cần tính.

• ~T~ dòng tiếp theo, mỗi dòng chứa một xâu có độ dài không quá ~10^5~ chỉ gồm các kí tự từ ~0~ đến ~9~ và ~\{+, -, *\}~ mô tả biểu thức cần tính.

  Dữ liệu đảm bảo không có hai dấu nào nằm cạnh nhau và dấu nhân ~(*)~ không xuất hiện ở đầu và cuối biểu thức.

Output

• In ra ~T~ dòng, mỗi số trên một dòng là giá trị của biểu thức tương ứng. Vì đáp án có thể rất lớn nên hãy in ra số dư khi chia cho ~123456789~.

Subtask

• ~50\%~ số test có các biểu thức đã cho không có phép nhân.

• ~50\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

5
+1+2+3+4
1+2*3+4
-1*2+3*4
1+2+3*4
1*2+3+4

Sample Output 1

10
11
10
15
9

Cho một ma trận ~a~ kích thước ~n \times m~, tìm hai dấu cộng không có điểm chung trên ma trận sao cho tổng giá trị nằm trên hai dấu cộng là lớn nhất.

Một dấu cộng là hai đoạn thẳng có độ dài lẻ và bằng nhau, một đoạn thẳng nằm ngang, một đoạn thẳng nằm dọc và giao nhau tại trung điểm.

Ảnh ví dụ.

Các hình màu xanh là dấu cộng, màu vàng không phải là dấu cộng.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ lần lượt là số hàng và số cột của ma trận ~a~ ~(2 \le n, m \le 15)~

• Trên ~n~ dòng sau, dòng thứ ~i~ chứa ~m~ số nguyên, số thứ ~j~ miêu tả ~a_{ij}~, giá trị của ô hàng ~i~ cột ~j~ ~(-10^6 \le a_{ij} \le 10^6)~

Output

• In ra trên một dòng một số nguyên duy nhất là kết quả của bài toán.

Subtask

• ~30\%~ số test có ~n, m \leq 3~.

• ~70\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

3 3
2 1 1
1 2 1
1 -1 -1

Sample Output 1

6

Note

Chọn hai dấu cộng sau:

• Dấu cộng thứ nhất có tâm ở đỉnh ~(2,2)~ và có độ lớn là ~3~ (độ lớn ở đây là độ dài của ~2~ đoạn thẳng trong dấu cộng đó). Tổng các phần tử nằm trong dấu cộng này là ~2+1+1+1+(-1)=4~.

• Dấu cộng thứ hai có tâm ở đỉnh ~(1,1)~ và có độ lớn là ~1~. Tổng các phần tử nằm trong dấu cộng này là ~2~.

Từ đó tổng tất cả các phần tử khi chọn cả ~2~ dấu cộng trên là ~4+2=6~. Có thể thấy được không có cách để chọn ~2~ dấu cộng ra tổng lớn hơn trong trường hợp trên.

Cho hai số nguyên dương ~X~ và ~Y~. ~X~ có giá trị bằng tích lũy thừa của ~n~ số nguyên tố ~p_1, p_2, ..., p_n~ với số mũ lần lượt là ~a_1, a_2, ..., a_n~ hay ~X~ = ~p_1^{a_1} \cdot p_2^{a_2} \cdot ... \cdot p_n^{a_n}~. ~Y~ có giá trị bằng tích lũy thừa của ~m~ số nguyên tố ~q_1, q_2, ..., q_m~ với số mũ lần lượt là ~b_1, b_2, ..., b_m~ hay ~Y~ = ~q_1^{b_1} \cdot q_2^{b_2} \cdot ... \cdot q_m^{b_m}~.

Hỏi có bao nhiêu số nguyên dương ~Z~ thỏa mãn các điều kiện:

• Là ước của số ~X~.

• Là bội của sô ~Y~.

• Tổng số mũ khi phân tích ra thừa số nguyên tố không vượt quá ~k~.

Vì kết quả có thể rất lớn, in ra số lượng số nguyên ~Z~ thỏa mãn chia lấy dư cho ~10^9+7~.

Input

• Dòng đầu tiên chứa số nguyên dương ~k~ ~(1 \leq k \leq 10^5)~.

• Dòng thứ hai chứa số nguyên dương ~n~ ~(1 \leq n \leq 100)~.

• Dòng thứ ba chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \leq a_i \leq 10^5)~.

• Dòng thứ tư chứa ~n~ số nguyên dương phân biệt ~p_1, p_2, ..., p_n~ ~(1 \leq p_i \leq 10^9)~.

• Dòng thứ năm chứa số nguyên dương ~m~ ~(1 \leq m \leq 100)~.

• Dòng thứ sáu chứa ~m~ số nguyên dương ~b_1, b_2, ..., b_m~ ~(1 \leq b_i \leq 10^5)~.

• Dòng cuối cùng chứa ~m~ số nguyên dương phân biệt ~q_1, q_2, ..., q_m~ ~(1 \leq q_i \leq 10^9)~.

Dữ liệu đảm bảo tổng số mũ của ~X~ là ~Y~ không vượt quá ~10^5~.

Output

• Một số duy nhất là số lượng số ~Z~ thỏa mãn sau khi chia lấy dư cho ~10^9+7~.

Subtask

• ~30\%~ số test có ~X, Y \leq 10^6~.

• ~30\%~ số test khác có tổng số mũ của ~X~ và ~Y~ không vượt quá ~k~.

• ~40\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

3
2
2 2
2 3
2
1 1
2 3

Sample Output 1

3

Note

Trong test ví dụ, ~X = 2^2 \times 3^2 = 36~, ~Y = 2 \times 3 = 6~. Các giá trị ~Z~ thỏa mãn là ~6~, ~12~ và ~18~.

Tết nguyên đán Giáp Thìn (2024) đã đến rất gần, nhưng Quân vẫn chưa chuẩn bị được cây đào chơi tết. Ban lãnh đạo VNOI vừa đưa ra chỉ thị cho Hội đồng Bedao contest mua đào về chơi tết. Biết cây đào này là đào thất thốn (Đào tiến vua), lại được lai tạo cho ra hoa đa sắc, Quân lân la hỏi chuyện và đã được Sếp cho phép chọn ra một gốc đào nhỏ mang về nhà trưng.

Cây đào có thể coi như một đồ thị dạng cây với n đỉnh, gốc của cây đào sẽ là đỉnh với thứ tự là ~1~. Các đỉnh của cây sẽ được nối với nhau bằng các cành. Khi mới mua về, trên mỗi đỉnh của cây đào sẽ có không quá một bông hoa (Do người bán muốn duy trì dưỡng chất cho cây). Theo dòng thời gian, có thể có một số sự kiện diễn ra:

• BLOOM ~x~ ~v~: Có một bông hoa đào màu ~x~ nở rộ trên đỉnh ~v~ của cây.

• DISSOLVE ~x~ ~v~: Một bông hoa màu ~x~ trên đỉnh ~v~ đã bị héo và rụng.

Để chọn được cành hoa ưng ý về chơi tết, Quân sẽ xen một số câu hỏi vào giữa các "sự kiện":

• TAKE ~u~ ~v~: Nếu Quân bẻ cành cây giữa hai đỉnh ~u~, ~v~ thì số màu hoa khác nhau mà quân mang về nhà là bao nhiêu ~?~

  Biết rằng khi bẻ cành cây, phần không chứa gốc sẽ là phần Quân được phép mang về, hay nói cách khác nếu như ~u~ là cha của ~v~ thì Quân sẽ mang cây con gốc ~v~ về nhà, ngược lại, Quân sẽ mang cây con gốc ~u~ về nhà. Dữ liệu đảm bảo có một cành nối giữa hai đỉnh ~u,\ v~ trên cây.

Bạn hãy giúp Quân trả lời các câu hỏi để anh có thể tìm được cành hoa ưng ý về trưng tết nhé.

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(1 \le n \le 5 \times 10^5)~ mô tả số sự kiện trong dòng thời gian.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1,\ a_2, \ldots,\ a_n~ ~(-1 \le a_i \le 10^6)~ với ~a_i~ là màu của bông hoa trên đỉnh ~i~ của cây (nếu ~a_i = -1~ thì trên đỉnh ~i~ không có bông hoa nào).

• ~n - 1~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~u,\ v~ ~(1 \le u,\ v \le n,\ u \neq v)~ mô tả một cành của cây đào.

• Dòng tiếp theo chứa một số nguyên dương ~q~ ~(1 \le q \le 5 \times 10^5)~ mô tả số sự kiện trong dòng thời gian.

• ~q~ nhóm dòng cuối nhóm dòng gồm ~2~ dòng:

  • Dòng đầu tiên chứa một xâu ~s~ và hai số nguyên ~x,\ v~ ~(0 \le x \le 2 \times 10^6,\ 0 \le v \le 2 \times 10^6)~ mô tả một sự kiện.

    Lưu ý: Vì thời gian qua đi không trở lại, nên gọi ~\it{ans}~ là câu trả lời cho câu hỏi trước đó của Quân (Nếu chưa có câu hỏi nào thì ~\it{ans} = 0~), màu của bông hoa sẽ là ~x' = x~ xor ~\it{ans}~ và đỉnh mà hoa nở sẽ là ~v'~ = ~v~ xor ~\it{ans}~

    Dữ liệu đảm bảo ~0 \le x' \le 10^6~ và ~1 \le v' \le n~

  • Dòng thứ hai chứa xâu TAKE và hai số nguyên ~u,\ v~ ~(1 \le u,\ v \le n,\ u \neq v)~ mô tả mội câu hỏi của Quân.

Output

• In ra ~q~ dòng, trên mỗi dòng in ra một số nguyên là đáp án cho câu hỏi tương ứng của Quân.

Subtask

• ~20\%~ số test của bài với ~n,\ q \le 5000~

• ~20\%~ số test khác của bài có màu của các bông hoa không giống nhau

• ~20\%~ số test khác cùa bài với ~u,\ v~ giống nhau trong mọi câu hỏi

• ~40\%~ số test còn lại không có điều kiện gì thêm

Sample Input 1

5
1 -1 3 -1 5
1 3
2 4
1 5
5 4
5
BLOOM 2 2
TAKE 4 5
DISSOLVE 2 2
TAKE 2 4
BLOOM 5 4
TAKE 1 3
DISSOLVE 5 5
TAKE 4 2
BLOOM 2 0
TAKE 1 5

Sample Output 1

1
1
0
1
2