Cho ba số thực ~a~, ~b~, ~c~. Kiểm tra xem ba số này có thể là độ dài ba cạnh của một tam giác được hay không.

Tổng độ dài 2 cạnh bất kì luôn lớn hơn độ dài cạnh còn lại.

Input

Gồm 3 dòng, mỗi dòng chứa một số thực lần lượt tương ứng với ~a~, ~b~, ~c~ (~a, b, c \leq 2 \times 10^9~).

Output

In ra YES nếu ba số ~a~, ~b~, ~c~ là độ dài ba cạnh của một tam giác, không thì in ra NO.

Sample Test 1

Input:

3
4
5

Output:

YES

Sample Test 2

Input:

2
3
1

Output:

NO

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

Số Fibonacci thứ ~i~ được định nghĩa như sau: ~ \begin{equation} f_i = \begin{cases} 1 & \text{nếu $i \leq 2$}\\ f_{i - 1} + f_{i - 2} & \text{nếu $i > 2$} \end{cases} \end{equation} ~

Ví dụ dãy Fibonacci cho ~10~ số đầu tiên: ~1, 1, 2, 3, 5, 8, 13, 21, 34, 55~.

Input

Gồm một số nguyên dương ~n~ duy nhất. (~n \leq 75~)

Output

In ra số Fibonacci thứ ~n~.

Subtasks

Subtask ~1~ (~40\%~): ~n \leq 40~.

Subtask ~2~ (~60\%~): Không có điều kiện gì thêm.

Sample Test 1

Input:

4

Output:

3

Sample Test 2

Input:

10

Output:

55

Tuấn có một chuỗi ký tự chỉ gồm các chữ cái thường tiếng Anh và đang cố mã hóa chuỗi này theo một mã hóa nhất định.

Mã hóa này được mô tả bởi hai chuỗi ~A~ và ~B~, trong đó mỗi ký tự ở chuỗi ~A~ được ánh xạ tới một ký tự tương ứng trong chuỗi ~B~. Ví dụ, nếu

• ~A = ~ abcdefghijklmnopqrstuvwxyz
• ~B = ~ zyxwvutsrqponmlkjihgfedcba,

thì a sẽ được ánh xạ thành z, b sẽ thành y, ....

Việc biến đổi chuỗi chỉ một lần thì khá nhàm chán, vì vậy, với một số nguyên dương ~K~, Tuấn muốn lặp lại quá trình mã hóa này ~K~ lần. Nhưng giờ đây Tuấn đã mệt và nhờ bạn giúp đỡ. Bạn có thể giúp Tuấn để có được chuỗi cuối cùng không?

Dữ liệu vào từ tệp văn bản: MAHOAXAU.INP

• Dòng đầu tiên chứa xâu ~S \ (1 \leq |S| \leq 10^5)~ chỉ gồm các kí tự La-tinh in thường.
• Dòng tiếp theo chứa một số nguyên dương ~K \ (1 \leq K \leq 10^9)~.
• Hai dòng tiếp theo, mỗi dòng chứa lần lượt hai xâu ~A~ và ~B~ có đúng ~26~ kí tự là hoán vị của các kí tự La-tinh in thường từ a đến z.

Kết quả ghi ra tệp văn bản: MAHOAXAU.OUT

• In ra một xâu duy nhất là kết quả bài toán.

Scoring

• Subtask 1 (~30 \%~ số điểm): ~K = 1~.
• Subtask 2 (~30 \%~ số điểm): ~K, |S| \leq 2000~.
• Subtask 3 (~20 \%~ số điểm): ~K \leq 10^5~.
• Subtask 4 (~20 \%~ số điểm): Không có ràng buộc gì thêm.

Sample Input

hnoi
2
abcdefghijklmnopqrstuvwxyz
pnudzgabijkyehlrqxfmsctovw

Sample Output

nbyi

Giải thích: Các kí tự của xâu hnoi được mã hóa như sau:

• h → b → n
• n → h → b
• o → l → y
• i → i → i

Cô giáo làng Kamishirasawa Keine nhặt được một cuốn sách lạ, hóa ra đó là sách dạy lập trình ở thế giới bên ngoài. Cô định mang về dạy cho các bạn nhỏ nhưng vì sách toàn bài tập khó nên cả cô vẫn chưa giải được. Chính vì thế cô nhờ bạn giúp giải bài toán sau:

Với mỗi số từ ~1~ đến ~9~ cho ~p_i~ là số lần xuất hiện của chữ số ~i~. Hãy tính tổng của tất cả các số khác nhau được tạo bởi những chữ số đã cho.

Input

• Dòng đầu tiên là số nguyên dương ~T \le 5000~ là số lượng test.
• ~T~ dòng tiếp theo mỗi dòng gồm 9 số nguyên ~0 \le p_i \le 9~.

Output:

• ~T~ dòng mỗi dòng là một số nguyên duy nhất là tổng các số có thể tạo được modulo ~10^9+7~.

Sample Test

Input:

3
0 0 0 1 0 0 0 1 0
0 0 0 1 0 1 0 2 0
1 2 0 2 1 1 1 0 1 

Output:

144
95818
689045052

• Giải thích: Ở test đầu tiên các số tạo ra được là: ~4 + 8 + 48 + 84 = 144~

Khu kiếm ăn của Rùa là một bảng gồm ~n~ dòng và ~m~ cột, trong các ô là số thức ăn của nó. Ban đầu rùa nằm trong hang: cửa hang là ô bên trái phía dưới cùng của bảng và nó cần di chuyển đến cuối khu vực kiếm ăn của nó là ô bên phải trên cùng của bảng. Mỗi bước con rùa chỉ có thể di chuyển sang ô kế bên phải hoặc phải trên. Hãy tìm con đường đi cho rùa để đạt được tổng lớn nhất.

INPUT

Dòng đầu là 2 số ~n~ và ~m~ (~1 \le n, m \le 1000~)

~n~ dòng tiếp theo mỗi dòng gồm ~m~ số nguyên (~0 \le a_{ij} \le 10^6~)

OUTPUT

Số nguyên duy nhất là tổng giá trị lớn nhất tìm được

SAMPLE INPUT

4 4
9 8 6 2
10 11 13 11 
3 7 12 8
5 9 13 9

SAMPLE OUTPUT

65