Có \(n\) món quà, món quà thứ \(i\) có giá trị là \(A_i\).

A sẽ tặng \(K\) món quà cho B.

Mỗi cách A tặng quà cho B có thể được biểu diễn bởi tập các chỉ số \(i_1, i_2, \ldots, i_K ~ (1 \leq i_1 < i_2 < \ldots < i_K \leq n)\). Và giá trị
của cách tặng quà này là \(\sum_{j=1}^{K} A_{i_j}\).

Hãy tính tổng giá trị của tất cả các cách tặng quà, chia dư cho \(({10^9} + 7)\).

Input

• Dòng đầu tiên chứa hai số \(n, K\) \((1 \leq K \leq n \leq 2 \times 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên, số thứ \(i\) là \(A_i ~ ( ~ |A_i| \leq 20242024 ~)\).

Output

• Một dòng duy nhất chứa tổng giá trị của các cách tặng quà, chia dư cho \(({10^9} + 7)\).

Scoring

• Subtask 1 (\(10\%\) số điểm): \(n \leq 10\).
• Subtask 2 (\(40\%\) số điểm): \(n \leq 1000\).
• Subtask 3 (\(50\%\) số điểm): \(n \leq 2 \times {10^5}\).

Example

3 2
1 2 3

12

Ban đầu có số \(X\), hai người luân phiên chơi, mỗi lượt một người phải lựa chọn một trong hai thao tác sau:

• Trừ \(X\) đi \(1\), \(X := X - 1\).
• Chia \(X\) cho một ước \(d\) của \(X\) mà \(d > 1\) và \(d < X\), \(X := \frac{X}{d}\).

Hai người luân phiên chơi, tức là lượt đầu tiên thì người thứ nhất chơi, lượt thứ hai thì người thứ hai chơi,
lượt thứ ba thì người thứ nhất chơi, lượt thứ tư thì người thứ hai chơi, và cứ thế ...

Sau lượt của người nào mà \(X = 1\) thì người đó thua cuộc.

Biết rằng cả hai người rất thông minh và đều chơi cách tối ưu nhất để không thua cuộc.

Cho \(q\) truy vấn, mỗi truy vấn cho một số \(X\). Hỏi rẳng nếu ban đầu có số \(X\) thì người đi đầu hay người đi sau chắc chắn thắng.

Input

• Dòng đầu tiên chứa một số nguyên dương \(q\) là số truy vấn.
• \(q\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(X\) tương ứng với một truy vấn.

Output

• Gồm \(q\) dòng, dòng thứ \(i\) chứa câu trả lời của truy vấn thứ \(i\), là một xâu kí tự là "First" hoặc "Second", tương ứng với người đi đầu hoặc người đi sau chắc chắn thắng.

Scoring

• Subtask 1 (\(20\%\) số điểm): \(q \leq 10, n \leq 20\).
• Subtask 2 (\(30\%\) số điểm): \(q \leq 50, n \leq {10^6}\).
• Subtask 3 (\(50\%\) số điểm): \(q \leq 50, n \leq {10^{10}}\).

Example

3
8
9
10

First
Second
First        

Cao Thanh Hùng là một anh chàng nghiện game có tiếng,anh ta luôn ngồi trong phòng của mình và cày game đến sáng,chính vì vậy anh ta vẫn ế đến tận bây giờ.
Chính vì thiếu gái ngoài đời nên Hùng đang cố tìm một game để xây dựng một dàn harem cho riêng mình.

Hùng đã tìm được một game khá thú vị để thoả mãn sở thích của mình.Game cho Hùng một dàn harem gồm \(n\) cô gái lần lượt có chỉ số xinh đẹp là \(a_1,a_2,...,a_n\).

Game còn cho Hùng một số nguyên \(x\) gọi là độ đẹp cân đối.

Độ đẹp của 1 dãy các cô gái là số dãy con liên tiếp nhiều nhất có thể chọn trong dãy mà các dãy con không giao nhau và trung bình cộng chỉ số xinh đẹp của mỗi dãy con đều bằng \(x\);

Hùng phải trả lời \(q\) câu hỏi game đưa ra để rước cả dàn harem này về cho mình

Câu hỏi thứ \(i\) gồm 2 số \(l_i\) và \(r_i\) yêu cầu Hùng tính độ đẹp của dãy harem \(a_{l_i}\)...\(a_{r_i}\).

Do bị bệnh ế đeo bám bao lâu nay nên đầu óc Hùng rất lú lẫn nên rất khó để trả lời các câu hỏi của game,bình thường những lúc này thì Hùng thường nhờ đến Vinh giúp đỡ (Vinh không ế nên rất tỉnh táo),mà đúng hôm nay Vinh lại bận đi chơi với bạn gái nên không giúp được.

Hùng đánh nhờ đến các bạn giúp đỡ, hãy giúp Hùng nhé !

Input

• Dòng thứ nhất gồm 3 số nguyên dương \(n,q,x ~ (n,q\le 2\times 10^5, ~x\le 10^6)\)
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1,a_2,...,a_n\) (\(a_i\le 10^6\))
• \(q\) dòng tiếp theo mỗi dòng gồm \(2\) số nguyên \(l_i\),\(r_i\) (\(1\le l_i\le r_i\le n\))

Output

• Gồm \(q\) dòng,dòng thứ \(i\) là đáp án của câu hỏi thứ \(i\).

Scoring

• Subtask 1 (\(30\%\) số điểm): \(n,q\le 500\);
• Subtask 2 (\(40\%\) số điểm): \(500\le n,q\le 5000\);
• Subtask 3 (\(30\%\) số điểm): Không có ràng buộc gì thêm;

Example

10 1 5
6 7 2 5 6 1 8 7 4 6
1 10

4

Ảo thuật gia trong một tiết mục của mình trình ra hai mảng \(S\) và \(T\) cùng có độ dài \(n\), chứa các số nguyên dương không vượt quá \(10^9\).

Sau đó, ông mời khán giả chọn ra một đoạn bắt đầu từ vị trí \(l\) và kết thúc tại vị trí \(r\) \((1 \leq l \leq r \leq n)\). Ảo thuật gia sẽ cắt ra hai đoạn \(S'\) và \(T'\) lần lượt là đoạn con của \(S\) và \(T\) từ vị trí \(l\) tới vị trí \(r\). Cuối cùng, ông ta sẽ thực hiện màn ảo thuật biến đổi đoạn \(S'\) thành \(T'\).

Tuy nhiên, vì là một ảo thuật gia tay ngang, nên công cụ của ông ta thiếu ổn định. Được biết, công cụ sẽ chỉ thực hiện biến đổi chuẩn xác 100\% khi và chỉ khi hai đoạn \(S'\) và \(T'\) thỏa mãn các điều kiện sau:

• Số lượng giá trị khác nhau trong hai đoạn \(S'\) và \(T'\) là bằng nhau
• Nếu tồn tại hai vị trí \(i \neq j\) sao cho \(S'_i = S'_j\), thì điều kiện này cũng phải được thỏa mãn sau khi biến đổi, tức \(T'_i = T'_j\).

Bạn hãy cho biết, có bao nhiêu đoạn \([l, r]\) mà khán giả có thể chọn để đảm bảo ảo thuật gia sẽ biến đổi chuẩn xác 100\%?

Input

• Dòng đầu tiên in ra số \(n\) \((n \leq 2 \times 10^5)\).
• Dòng thứ hai in ra \(n\) số nguyên \(S_1, S_2, \dots, S_n\) \((1 \le S_i \le 10^9)\)
• Dòng thứ ba in ra \(n\) số nguyên \(T_1, T_2, \dots, T_n\) \((1 \le T_i \le 10^9)\)

Output

• In ra một dòng duy nhất là số đoạn \([l, r]\) thỏa mãn.

Scoring

• Subtask 1 (10\%): \(n \leq 50\)
• Subtask 2 (15\%): \(n \leq 400\)
• Subtask 3 (25\%): \(n \leq 5000\)
• Subtask 4 (15\%): \(\forall i: S_i, T_i \leq 2\)
• Subtask 5 (20\%): \(\forall i: S_i, T_i \leq 64\)
• Subtask 6 (15\%): Không có điều kiện gì thêm.

Example

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

18