Yêu cầu

Cho một dãy gồm ~N~ số nguyên ~A_1, A_2, A_3, ..., A_N~, hãy tìm trong dãy số trên một số nguyên bằng tổng tất cả các số nguyên còn lại.

Dữ liệu

• Dòng đầu tiên ghi một số nguyên dương ~N~ ( ~2 \leq N \leq 200~ ).
• Dòng tiếp theo ghi ~N~ số nguyên dương ~A_i~ ( ~|A_i| \leq 10^9~ ).

Kết quả

• In ra một số nguyên tìm được trong dãy số đã cho thỏa mãn yêu cầu đề bài.
• Trường hợp không có số nào trong dãy thỏa mãn yêu cầu đề bài thì in ra một kí tự N.

VD

Test mẫu 1:

INPUT

4
-2 5 3 6

OUTPUT

6

Test mẫu 2:

INPUT

3
2 3 4

OUTPUT

N

Dãy số Fibonacci được Fibonacci, một nhà toán học người Ý, công bố vào năm 1202 trong cuốn sách Liber Abacci - Sách về toán đồ qua 2 bài toán: Bài toán con thỏ và bài toán số các "cụ tổ" của một ong đực. Bạn có thể tham khảo về dãy Fibonacci tại đây: wikipedia.

Chung quy lại dãy Fibonacci được định nghĩa là dãy số có công thức: ~F_1 = F_2 = 1; F_n = F_{n-1} + F_{n-2}~ với mọi số nguyên n lớn hơn 2. Một vài số hạng đầu tiên của dãy như sau: ~1, 1, 2, 3, 5, 8, 13, 21, ...~ Hôm nay ta sẽ xem xét một tính chất khá thú vị cho dãy Fibonacci. Trong bài toán này ta chỉ đơn giản tính số Fibonacci thứ ~n~, nhưng vì số này tăng rất nhanh nên ta sẽ chia lấy dư cho ~10^9 + 7~ khi in ra.

Yêu cầu:

Cho một số nguyên dương ~n~, hãy tính số Fibonacci thứ ~n~, kết quả chia lấy dư cho ~10^9 + 7~ khi in ra.

Input Specification

• Một dòng duy nhất ghi số nguyên dương ~n~ (~0 \le n \le 10^6~)

Output Specification

• In ra số Fibonacci thứ ~n~, kết quả chia lấy dư cho ~10^9 + 7~.

Sample Input

7

Sample Output

13

Giải thích: Số Fibonacci thứ 7 là 13

Yêu cầu

Ta định nghĩa dãy Fibonacci như sau: ~F[0] = F[1] = 1; F[n] = F[n - 1] + F[n - 2];~

Cho một số nguyên dương ~n,~ hãy tính số Fibonacci thứ ~n~.

Dữ liệu

• Dòng đầu tiên ghi số nguyên ~q\ (1 \leq q \leq 10^5)~là số truy vấn
• ~q~ dòng tiếp theo, mỗi dòng ghi một số nguyên dương ~n~ (~0 \le n \le 92~)

Kết quả

• Ứng với mỗi truy vấn, in ra số Fibonacci ~F[n]~ trên mỗi dòng tương ứng.

Ví dụ

Giải thích: F[0] = F[1] = 1, F[2] = 2, F[3] = 3, F[4] = 5, F[5] = 8, F[6] = 13, F[7] = 21

Dãy số Fibonacci được định nghĩa là:

• ~F_1 = F_2 = 1~;
• ~F_i = F_{i-1} + F_{i-2}~ ~(i \geq 3)~.

Yêu cầu

Cho một số nguyên dương ~N~, in ra ~F_N~ ~mod~ ~(10^9 + 7)~ nghĩa là lấy kết quả chia lấy dư cho ~1000000007~.

Dữ liệu

• Dòng đầu tiên gồm một số nguyên dương ~T~ chỉ số lượng testcase ~(T \leq 10^5)~.
• $T$ dòng tiếp theo, mỗi dòng gồm một số nguyên dương ~N~ ~(N \leq 10^6)~.

Kết quả

In ra ~T~ dòng tương ứng với kết quả của mỗi ~N~ trong ~T~ câu hỏi.

Ví dụ

INPUT

3
1
3
5

OUTPUT

1
2
5

Dãy Fibonacci được định nghĩa như sau:

~F_k = k~ nếu ~0\le k\le 1~.

~F_k = F_{k-1} + F_{k-2}~ nếu ~k > 1~.

Một vài số hạng đầu tiên của dãy: 0; 1; 1; 2; 3; 5; 8; 13; 21; 34; 55;.....

Yêu cầu

Viết chương trình kiểm tra xem một số nguyên có thể được viết thành tích của 2 số trong dãy Fibonacci hay không.

Dữ liệu

• Dòng đầu tiên gồm 1 số nguyên ~t\ (1 \leq t \leq 10)~, là số số nguyên cần kiểm tra.
• ~t~ dòng tiếp theo, dòng thứ ~i~ ghi số nguyên ~n_i\ (0 \leq n_i \leq 10^9)~.

Kết quả

Gồm ~t~ dòng, dòng thứ ~i~ ghi YES nếu ~n_i~ có thể phân tích thành tích của 2 số trong dãy Fibonacci, nếu không thì ghi NO.

Ví dụ

Dãy số Fibonacci được Fibonacci, một nhà toán học người Ý, công bố vào năm 1202 trong cuốn sách Liber Abacci - Sách về toán đồ qua 2 bài toán: Bài toán con thỏ và bài toán số các "cụ tổ" của một ong đực. Bạn có thể tham khảo về dãy Fibonacci tại đây: wikipedia.

Chung quy lại dãy Fibonacci được định nghĩa là dãy số có công thức: F1 = F2 = 1, Fn = F(n-1) + F(n-2) với mọi số nguyên n lớn hơn 2. Một vài số hạng đầu tiên của dãy như sau: 1, 1, 2, 3, 5, 8, 13, 21, ...Có rất nhiều vấn đề Toán học, Kinh tê, Thế giới tự nhiên tuân theo quy luật của dãy số này. Hôm nay ta sẽ xem xét một tính chất khá thú vị cho dãy Fibonacci. Người ta chứng minh được rằng, với mọi số nguyên dương X đều phân tích được dưới dạng tổng của các số Fibonacci khác nhau. Ví dụ: 7 = 2 + 5, 10 = 2 + 8 = 2 + 3 + 5.

Yêu cầu:

Cho một số nguyên dương X, hãy tính xem cần ít nhất bao nhiêu số Fibonacci khác nhau để tổng của chúng bằng X.

Input Specification

• Một dòng duy nhất ghi số nguyên dương ~X~ (~0 \le X \le 10^9~)

Output Specification

• In ra số lượng ít nhất các số Fibonacci có tổng bằng ~X~.

Sample Input

17

Sample Output

3

Giải thích: 17 = 13 + 3 + 1

Cho dãy số nguyên ~a~ gồm ~n~ phần tử ~a_1,a_2,...,a_n~ và ~Q~ truy vấn.

Mỗi truy vấn là số nguyên dương ~i~, hãy in ra tổng đoạn con từ ~a_1~ đến ~a_i~.

Input

• Dòng đầu chứa số nguyên dương ~n~.
• Dòng 2 chứa ~n~ số nguyên mô tả dãy ~a~.
• Dòng 3 chứa số nguyên dương ~Q~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa số nguyên ~i(i\leq n)~.

Output

• Gồm ~Q~ dòng, mỗi dòng là tổng đoạn con cần tìm.

Constraints

• ~n\leq 10^5~
• ~|a_i|\leq 100~
• ~Q\leq 10^5~

Example

Cho dãy số nguyên~a~ gồm ~n~ phần tử ~a_1,a_2,...,a_n~ và ~Q~ truy vấn.

Mỗi truy vấn là một cặp số nguyên dương ~(L, R)~, hãy in ra tổng đoạn con từ ~a_L~ đến ~a_R~.

Input

• Dòng đầu chứa số nguyên dương ~n~.
• Dòng 2 chứa ~n~ số nguyên mô tả dãy ~a~.
• Dòng 3 chứa số nguyên dương ~Q~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa cặp số nguyên ~L, R(L\leq R\leq n)~.

Output

• Gồm ~Q~ dòng, mỗi dòng là tổng đoạn con cần tìm.

Constraints

• ~n\leq 10^5~
• ~|a_i|\leq 100~
• ~Q\leq 10^5~

Example

Cho dãy số nguyên ~a~ gồm ~n~ phần tử ~a_1,a_2,...,a_n~ và số nguyên ~k~.

Hãy đếm xem có bao nhiêu đoạn con liên tiếp có tổng đúng bằng ~k~.

Input

• Dòng đầu chứa số nguyên dương ~n~ và số nguyên ~k~.
• Dòng 2 chứa ~n~ số nguyên mô tả dãy ~a~.

Output

• In ra kết quả bài toán.

Constraints

• ~n\leq 5000~
• ~|a_i|\leq 10^{15}~
• ~k\leq 10^{18}~

Example

Sample input

5 6
2 2 2 3 3

Sample output

2

Giải thích: Có 2 đoạn con có tổng bằng 6 là: 2 2 2 và 3 3

An và Bình là hai anh em. Ba của An sau chuyến đi công tác xa nhà trở về, mua cho An và Bình ~N~ gói kẹo, gói thứ ~i~ có ~A_i~ viên kẹo.

Để tránh việc tranh giành kẹo lẫn nhau, ba của An đã thống nhất việc chia kẹo theo cách sau:

• Trước hết, ba của An chọn ra một số nguyên ~k~ (với ~1 ≤ k ≤ N).~
• An sẽ được chia các gói kẹo từ ~1~ đến ~k~. Phần còn lại (các gói kẹo từ ~k~ + ~1~ đến ~N~) sẽ được chia cho Bình.

Để tránh sự phân bua giữa hai anh em, ba của An muốn lựa chọn chỉ số ~k~ sao cho chênh lệch giữa tổng số lượng viên kẹo của hai anh em là nhỏ nhất có thể. Hãy giúp ông thực hiện điều này.

Dữ liệu

• Dòng đầu tiên gồm số nguyên ~N~ ~(2 ≤ N ≤ 200000)~ - số gói kẹo.
• Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, ..., A_N~ ~(1 ≤ A_i ≤ 10^9)~ - số viên kẹo trong từng gói kẹo.

Kết quả

• In ra chênh lệch lượng kẹo nhỏ nhất có thể.

Ví dụ

Chấm điểm

• Subtask 1 (50% số điểm): ~N ≤ 2000~
• Subtask 3 (50% số điểm): Không có ràng buộc gì thêm