Cho một dãy số gồm ~n~ phần tử. Tìm độ dài của dãy con tăng dài nhất. Một dãy con được tạo bằng cách xóa đi một vài phần tử (hoặc không xóa) khỏi dãy ban đầu.

Yêu cầu: Tìm độ dài của dãy con tăng dài nhất.

Input

• Dòng thứ nhất chứa một số nguyên dương ~n~ (~n \leq 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,...,a_n~ (~|a_i| \leq 10^9~).

Output

Kết quả cần tìm - độ dài của dãy con tăng dài nhất của dãy ~a~.

Scoring

• Subtask ~1~ ~(20\%)~: ~n \leq 20~;
• Subtask ~2~ ~(30\%)~: ~n \leq 2000~;
• Subtask ~3~ ~(50\%)~: ~n \leq 10^5~.

Example input 1

5
2 1 4 3 5

Example output 1

3

Hôm nay, Nam đã học được một bài toán mới, đó chính là số Fibonacci. Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0 hoặc 1 và 1, các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó. Công thức truy hồi của dãy Fibonacci là: $$ F(n) = \begin{cases} 1, & \text{khi } n = 1; \\ 1, & \text{khi } n = 2; \\ F(n - 1) + F(n - 2), & \text{khi } n > 2. \end{cases} $$

Cô giáo của Nam đã giao ra một bài toán mới thật hốc búa dành cho Nam như sau: Hãy tìm số Fibonacci thứ ~n~ (~n \leq 10^6~).

Yêu cầu:Tìm số Fibonacci thứ ~n~.

Input

Chỉ có một dòng duy nhất gồm một số nguyên dương ~n~ (~n \leq 10^6~).

Output

Số tự nhiên - số Fibonacci thứ ~n~ modulo ~10^9+7~.

Example input 1

10

Example output 1

55

Note 1

• Các số Fibonacii như sau: ~1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...~

Cho một dãy số gồm ~n~ phần tử. Tìm đoạn con có tổng lớn nhất của dãy ~a~.

Yêu cầu: Tìm ra tổng lớn nhất mà tìm được.

Input

• Dòng thứ nhất gồm một số nguyên dương ~n~ (~n \leq 10^6~).
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...a_n~ (~|a_i| \leq 10^9~).

Output

Một số nguyên là tổng lớn nhất của đoạn con của dãy ~a~.

Example input 1

8
-2 1 -3 4 -1 2 1 -5 4

Example output 1

6

Note 1

• Đoạn con có tổng lớn nhất là ~[4, -1, 2, 1]~.
• Tổng của đoạn ~[4, -1, 2, 1]~ là ~6~.

Có ~n~ bậc thang. Mỗi lần, Nam có thể bước ~1~ bậc hoặc ~2~ bậc. Hỏi có bao nhiêu cách khác nhau để đi hết ~n~ bậc thang?

Yêu cầu: Tính và in ra số cách để leo hết ~n~ bậc thang.

Input

Một số nguyên dương ~n~ (~n \leq 10^6~).

Output

Một số nguyên dương duy nhất là số cách để leo hết ~n~ bậc thang modulo ~10^9+7~.

Scoring

• Subtask ~1~ ~(60\%)~: ~n \leq 20~;
• Subtask ~2~ ~(40\%)~: ~n \leq 10^6~.

Example input 1

4

Example output 2

5

Note 1

• Các cách đi:
  • ~1 + 1 + 1~.
  • ~1 + 1 + 2~.
  • ~1 + 2 + 1~.
  • ~2 + 1 + 1~.
  • ~2 + 2~.

~→~ Có ~5~ cách.

Có ~n~ ngôi nhà nằm trên một hàng. Mỗi ngôi nhà thứ ~i~ có một lượng tiền là ~a_i~. Bạn là một tên trộm thông minh - không thể trộm hai nhà kề nhau, vì như vậy sẽ bị phát hiện. Hãy tìm số tiền lớn nhất bạn có thể trộm được

Yêu cầu: Tính giá trị lớn nhất của tổng tiền có thể lấy, sao cho không có hai ngôi nhà nào kề nhau đều bị trộm.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \leq n \leq 10^6~)- số lượng ngôi nhà.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,...,a_n~ , ~a_i~ (~1 \leq i \leq n,1 \leq a_i \leq 10^9~) là số tiền trong từng ngôi nhà.

Output

Một số nguyên dương duy nhất là số tiền lớn nhất mà bạn có thể trộm được.

Scoring

• Subtask ~1~ ~(30\%)~: ~n \leq 20, 1 \leq a_i \leq 1000~;
• Subtask ~2~ ~(70\%)~: ~n \leq 10^6, 1\leq a_i \leq 10^9~.

Example input 1

5
2 7 9 3 1

Example output 1

12

Note 1

• Tên trộm lấy tiền ở nhà số 2 và 4 → ~7 + 3 = 10~.
• Nhưng tốt hơn là nhà ~2~ và ~3 → 7 + 9 = 16~ (sai vì kề nhau).
• Đúng tối ưu là nhà ~2~ và ~5 → 7 + 1 = 8~ hoặc nhà ~1 + 3 + 5 = 2 + 9 + 1 = 12~.

→ Đáp án: ~12~.

Cho ~n~ ngôi nhà được xếp thành một vòng (nghĩa là nhà ~1~ và nhà ~n~ cũng liền kề nhau) và mỗi nhà đều có số tiền nhất định.

Bạn là một tên trộm thông minh, nhưng không thể trộm hai nhà liền kề nhau.

Hãy tìm số tiền lớn nhất bạn có thể trộm được sao cho không trộm hai nhà liền kề nhau.

Yêu cầu:Tính số tiền mà bạn có thể trộm nhiều nhất.

Input

• Dòng thứ nhất chỉ có một số nguyên dương ~n~ - số lượng nhà (~1 \leq n \leq 10^6~).
• Dòng thứ hai có ~n~ số nguyên dương ~a_1,a_2,...,a_n~ - ~a_i~ số tiền của nhà thứ ~i~ (~1 \leq a_i \leq 10^9~).

Output

Một số nguyên duy nhất — số tiền lớn nhất mà tên trộm có thể lấy được khi các ngôi nhà xếp thành vòng tròn.

Example input 1

4
2 3 2 5

Example output 1

8

Tổ hợp là cách chọn một tập hợp con gồm ~k~ phần tử từ một tập hợp lớn gồm ~n~ phần tử, mà không quan tâm đến thứ tự sắp xếp của các phần tử đã chọn.

Bạn hãy tính giá trị của ~C(k, n)~ ~mod~ ~m~, tức là giá trị của tổ hợp chập ~k~ của ~m~ lấy theo modulo ~m~.

Yêu cầu: Tính ~C(k,n)~ ~mod~ ~m~ = ~\frac{n!}{k!*(k-n)!}~ ~mod~ ~m~.

Input

Nhập vào ba số tự nhiên ~k,n,m~ (~k,n,m \leq 2000~).

Output

Một số tự nhiên duy nhất, là giá trị ~C(k,n)~ ~mod~ ~m~.

Scoring

• Subtask ~1~ ~(40\%)~: ~k,n,m \leq 20~;
• Subtask ~2~ ~(60\%)~: ~k,n,m \leq 2000~.

Example input 1

5 2 10

Example output 1

0

Note 1

• ~C(5,2)=\frac{5!}{2!*(5-2)!}=\frac{5!}{2!*3!}=10~.

• ~C(5,2)~ ~mod~ ~10~ ~=~ ~10~ ~mod~ ~10~ ~=~ ~0~.

Xâu nhị phân là xâu chỉ chứa ~0~ và ~1~. Các xâu nhị phân có độ dài bằng ~n~ có ~2^n~ xâu nhị phân. Hãy đếm xem có bao nhiêu xâu nhị phân có độ dài ~n~.

Yêu cầu: Tính xem có bao nhiêu xâu nhị phân có độ dài ~n~.

Input

Nhập một số tự nhiên ~n~ (~n \leq 10^6~).

Output

Một đáp án - số lượng xâu nhị phân có độ dài ~n~ modulo ~10^9+7~.

Scoring

• Subtask ~1~ ~(20\%)~: ~(n \leq 20)~;
• Subtask ~2~ ~(80\%)~: ~(n \leq 10^6)~.

Example input 1

3

Example output 2

8

Note 1

• Có ~8~ xâu nhị phân có độ dài ~3~ là: ~000~, ~001~, ~010~, ~011~, ~100~, ~101~, ~110~, ~111~.

Cho ~k~ loại mệnh giá (đồng) như sau: ~c_1,c_2,...,c_k~. Hỏi có bao nhiêu cách để tạo ra số tiền ~S~ từ các mệnh giá đã cho, mỗi mệnh giá có thể dùng vô số lần?

Input

• Dòng thứ nhất có hai số tự nhiên ~k,S~ - số lượng mệnh giá và tổng tiền cần đổi.
• Dòng thứ hai gồm ~k~ số nguyên ~c_1,c_2,...,c_k~ , ~c_i~ (~1 \leq c_i \leq 10^5~) các mệnh giá tiền (mỗi mệnh giá đều khác nhau).

Output

Một số nguyên duy nhất - số cách tạo ra tổng tiền ~S~ lấy modulo cho ~10^9+7~.

Scoring

• Subtask ~1~ ~(10\%)~: ~S \leq 100, k \leq 5, 1 \leq c_i \leq 1000~;
• Subtask ~2~ ~(90\%)~: ~S \leq 10^6, k \leq 100, c_i \leq 10^6~.

Example input 1

3 5
1 2 5

Example output 1

4

Note 1

• Có ~4~ cách để tạo ra tổng ~5~:
  • ~1+1+1+1+1~.
  • ~1+1+1+2~.
  • ~1+2+2~.
  • ~5~.

Cho ~k~ loại mệnh giá (đồng) như sau: ~c_1,c_2,...,c_k~. Tìm số lượng đồng xu ít nhất để tạo ra số tiền ~S~, mỗi mệnh giá có thể dùng vô số lần?

Input

• Dòng thứ nhất có hai số tự nhiên ~k,S~ - số lượng mệnh giá và tổng tiền cần đổi.
• Dòng thứ hai gồm ~k~ số nguyên ~c_1,c_2,...,c_k~ , ~c_i~ (~1 \leq c_i \leq 10^5~) các mệnh giá tiền (mỗi mệnh giá đều khác nhau).

Output

Một số nguyên duy nhất - số lượng đồng xu ít nhất tạo ra tổng tiền ~S~ lấy modulo cho ~10^9+7~. Nếu không có cách chia nào thì in ra ~-1~.

Scoring

• Subtask ~1~ ~(10\%)~: ~S \leq 100, k \leq 5, 1 \leq c_i \leq 1000~;
• Subtask ~2~ ~(90\%)~: ~S \leq 10^6,k \leq 100, 1 \leq c_i \leq 10^6~.

Example input 1

3 11
1 5 7

Example output 1

3

Note 1

• Cách tối ưu: ~5 + 5 + 1 = 11~

→ Có ít nhất ~3~ đồng xu để tạo ra ~11~ đồng tiền

Có ~n~ cọc hàng rào được xếp thẳng hàng và ~k~ màu sơn khác nhau. Bạn cần sơn các cọc sao cho không có quá 2 cọc liên tiếp cùng màu. Hãy tính số cách sơn hợp lệ.

Yêu cầu: Tính và đưa ra số cách sơn hợp lệ cho ~n~ cọc hàng rào.

Input

Một dòng chứa hai số nguyên dương ~n,k~ (~1 \leq n,k \leq 10^5~).

Output

In ra số cách sơn thõa mãn yêu cầu, lấy modulo ~10^9+7~.

Scoring

• Subtask ~1~ ~(45\%)~: ~n,k \leq 1000~;
• Subtask ~2~ ~(55\%)~: ~n,k \leq 10^5~.

Example input 1

3 2

Example output 1

6

Note 1

• Với ~n~= 3, ~k~ = 2 (hai màu: A, B):
  • AAB, ABA, ABB, BAA, BAB, BBA → tổng cộng có 6 cách.
• Không được có AAA hoặc BBB vì có 3 cọc cùng màu liên tiếp.

Cho giá cổ phiếu của một công ty trong ~n~ ngày, được biểu diễn bởi ~a_1, a_2, \ldots, a_n~, trong đó ~a_i~ là giá cổ phiếu vào ngày thứ ~i~.

Bạn chỉ được phép thực hiện đúng một giao dịch, bao gồm:

• Mua vào một ngày nào đó ~i~.
• Bán ra vào một ngày sau đó ~j~ (~j > i~).

Hãy tìm lợi nhuận tối đa có thể đạt được từ giao dịch này. Nếu không thể thu được lợi nhuận (tức là giá luôn giảm), kết quả là ~0~.

Scoring

• Subtask ~1~ ~(50\%)~: ~n \leq 2000~, ~1 \leq a_i \leq 10^9~;
• Subtask ~2~ ~(50\%)~: ~n \leq 10^5~, ~1 \leq a_i \leq 10^9~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ - số ngày (~1 \leq n \leq 10^5~).
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \leq a_i \leq 10^9~) - giá cổ phiếu từng ngày.

Output

Một số nguyên duy nhất - lợi nhuận tối đa có thể đạt được.

Example input 1

6
7 1 5 3 6 4

Example output 1

5

Note 1

• Mua vào ngày 2 (có giá là 1) và bán vào ngày 5 (có giá là 6).
• Lợi nhuận: ~6 - 1 = 5~.

Cho một lưới có kích thước ~m*n~. Bạn bắt đầu từ ô ~(1,1)~ và muốn đi đến ô ~(m,n)~. Mỗi lần, bạn chỉ được đi sang phải hoặc đi xuống. Hãy đếm số cách đi từ ~(1,1)~ đến ~(m,n)~.

Yêu cầu: Đếm số đường đi từ ~(1,1)~ đến ~(m,n)~.

Input

Nhập hai số nguyên dương ~m,n~ (~1 \leq m,n \leq 1000~), là kích thước của lưới.

Output

Một số nguyên duy nhất, là số cách đi từ ~(1,1)~ đến ~(m,n)~. moudulo cho ~10^9+7~.

Example input 1

2 3

Example output 1

3

Note 1

• Các đường đi có thể là:
  • Phải → Phải → Xuống.
  • Phải → Xuống → Phải.
  • Xuống → Phải → Phải.

Cho một lưới kích thước ~m*n~, trong đó một số ô có vật cản mà robot không thể đi vào. Robot bắt đầu tại ô ~(1,1)~ và muốn di chuyển đến ô ~(m,n)~. Tại mỗi bước, robot chỉ được phép đi sang phải hoặc đi xuống dưới. Hãy tính số cách khác nhau để robot đi từ ô ~(1,1)~ đến ~(m,n)~ mà không đi vào ô có vật cản. Nếu không có đường đi nào hợp lệ thì in ra ~0~.

Yêu cầu: Tính số cách khác nhau để robot đi từ ô ~(1,1)~ đến ~(m,n)~ mà không đi vào ô có vật cản.

Input

• Dòng đầu tiên chứa hai số nguyên ~(m,n)~ - kích thước của lưới (~1 \leq m,n \leq 1000~).
• ~m~ dòng tiếp theo, mỗi dòng gồm ~n~ ký tự như sau:
  • . biểu thị ô trống - có thể đi qua.
  • # biểu thị ô có vật cản - không thể đi qua.

Output

Một số nguyên dương - số cách mà robot đi từ ~(1,1)~ đến ~(m,n)~ không đi vào ô có vật cản modulo ~10^9+7~.

Example input 1

3 4
....
.#..
....

Example output 1

4

Note 1

• Có 4 đường đi hợp lệ từ ~(1,1)~ đến ~(3,4)~ tránh vật cản ở ~(2,2)~.

Cho một ma trận nhị phân kích thước ~m*n~ (chỉ gồm các số ~0~ và ~1~). Hãy tìm diện tích của hình vuông lớn nhất chỉ chứa toàn các số ~1~.

Yêu cầu: Tìm diện tích của hình vuông lớn nhất trong ma trận chỉ chứa các số ~1~.

Input

• Dòng đầu tiên chứa hai số nguyên ~m~ và ~n~ - kích thước của trận (~m,n \leq 1000~).
• ~m~ dòng tiếp theo, mỗi dòng gồm ~n~ số (~0~ hoặc ~1~) cách nhau bởi khoảng trắng

Output

In ra diện tích của hình vuông lớn nhất chỉ gồm toàn các số ~1~.

Example input 1

5 6
0 1 1 0 1 0
1 1 1 1 1 1
0 1 1 1 1 1
1 1 1 1 1 1
0 1 1 1 1 0

Example output 2

16

Cho ~n~ đồ vật, mỗi vật có trọng lượng ~w_i~ và giá trị ~v_i~. Cho một cái có sức chứa ~W~. Chọn một số đồ vật cho vào túi sao cho tổng trọng lượng không vượt quá ~W~ và tổng giá trị là lớn nhất. Mỗi vật chỉ có thể chọn một lần.

Yêu cầu: In ra tổng giá trị lớn nhất có thể đạt được khi cho các đồ vật vào túi.

Input

• Dòng đầu tiên: hai số nguyên ~n~ và ~W~ - số lượng đồ vật và sức chứa của túi (~1 \leq n,W \leq 1000~).
• ~n~ dòng tiếp theo: mỗi dòng gồm hai số nguyên ~w_i~ và ~v_i~ - trọng lượng và giá trị của đồ vật thứ ~i~ (~1 \leq w_i \leq W, 1 \leq v_i \leq 10^9~).

Output

In ra tổng giá trị lớn nhất có thể đạt được khi cho các đồ vật vào túi.

Scoring

• Subtask ~1~ ~(70\%)~: ~1 \leq n \leq 20,1 \leq W \leq 1000~;
• Subtask ~2~ ~(30\%)~: Không rằng buộc giới hạn gì thêm.

  Example input 1

4 8
2 3
3 4
4 5
5 6

Example output 2

10

Note 1

• Chọn các đồ vật có trọng lượng 3 và 5 → tổng trọng lượng 8, tổng giá trị 10 (lớn nhất).

Cho ~n~ đồ vật, mỗi đồ vật có trọng lượng ~w_i~ , giá trị ~v_i~ và một chiếc túi có sức chứa tối đa ~W~.

Bạn có thể chọn mỗi đồ vật nhiều lần (không giới hạn số lượng). Hãy chọn các đồ vật sao cho tổng trọng lượng không vượt quá ~W~ và tổng giá trị là lớn nhất có thể.

Yêu cầu: Tìm giá trị lớn nhất có thể đạt được khi chọn một số (có thể lặp lại) các đồ vật, sao cho tổng trọng lượng không vượt quá sức chứa của túi ~W~.

Input

• Dòng thứ nhất: Hai số nguyên ~n,W~ - số lượng đồ vật và sức chứa túi (~1 \leq n,W \leq 1000~).
• ~n~ dòng tiếp theo chứa hai số ~w_i,v_i~ - trọng lượng và giá trị của vật thứ ~i~ (~1 \leq w_i \leq W, 1 \leq v_i \leq 10^9~).

Output

Một số nguyên duy nhất: giá trị lớn nhất có thể đạt được khi chọn đồ vật theo quy tắc trên.

Scoring

• Subtask ~1~ ~(70\%)~: ~1 \leq n \leq 20,1 \leq W \leq 1000~;
• Subtask ~2~ ~(30\%)~: Không rằng buộc giới hạn gì thêm.

  Example input 1

3 10
3 6
4 8
5 10

Example output 2

20

Note 1

• Chọn hai vật có trọng lượng 5, giá trị 10 → tổng = 10, giá trị = 20.
• Không có cách nào khác đạt giá trị cao hơn.

Cho một dãy gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~.

Hỏi có thể chia bao nhiêu dãy này thành hai tập con có tổng bằng nhau hay không?

Yêu cầu:

• In ra YES nếu có thể chia dãy thành hai tập con có tổng bằng nhau.
• Ngược lại, in ra NO.

Input

• Dòng thứ nhất có một số nguyên dương ~n~ - số lượng phần tử trong dãy (~1 \leq n \leq 100~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,...,a_n~ (~1 \leq a_i \leq 1000~).

Output

• In ra YES nếu có thể chia dãy thành hai tập con có tổng bằng nhau.
• Ngược lại, in ra NO.

Example input 1

4
1 5 11 5

Example output 1

YES

Note 1

• Có thể chia thành hai tập con:
  • Tập thứ nhất: ~{11}~.
  • Tập thứ hai: ~{5,5,1}~. → Tổng mỗi tập đều là 11.

Example input 2

3
1 2 5

Example output 2

NO

Note 2

• Không thể chia thành hai tập con có tổng bằng nhau.

Cho hai xâu ~s_1~ và ~s_2~ chỉ chứa các ký tự chữ cái Latin (~a-z, A-Z~).

Hãy tìm độ dài của dãy con chung dài nhất của chúng.

Yêu cầu: Tính và in ra độ dài của dãy con chung dài nhất của hai chuỗi ~s_1~ và ~s_2~.

Input

• Dòng thứ nhất: Chuỗi ký tự ~s_1~ (~1 \leq |s_1| \leq 2000~).
• Dòng thứ hai: Chuỗi ký tự ~s_2~ (~1 \leq |s_2| \leq 2000~).

Output

Một số nguyên duy nhất — độ dài của dãy con chung dài nhất của hai chuỗi.

Example input 1

ABCBDAB
BDCAB

Example output 1

4

Note 1

• Các dãy con chung dài nhất có thể là: BCAB, BDAB. → Độ dài của dãy con chung dài nhất là ~4~.

Cho hai chuỗi ký tự ~s_1~ và ~s_2~ chỉ chứa các ký tụ là chữ cái Latin (~a-z, A-Z~).

Hãy tìm số phép lần biến đổi ít nhất cần thực hiện để biến chuỗi ~s_1~ thành chuỗi ~s_2~.

Các phép biến đổi cho phép gồm:

• Thêm một ký tự vào chuỗi.
• Xóa một ký tự ra khỏi chuỗi.
• Thay thế một ký tự bằng ký tự khác.

Yêu cầu: Tính và in ra số phép biến đổi tối thiểu cần để biến ~s_1~ thành ~s_2~.

Input

• Dòng thứ nhất: Chuỗi ký tự ~s_1~ (~1 \leq |s_1| \leq 2000~).
• Dòng thứ hai: Chuỗi ký tự ~s_2~ (~1 \leq |s_2| \leq 2000~).

Output

Một số nguyên duy nhất — khoảng cách edit nhỏ nhất giữa hai chuỗi.

Example input 1

raccoonoj
clueoj

Example output 1

3

Note 1

• Biến đổi raccoonoj → clueoj như sau:
  • raccoonoj → accoonoj (xóa r tại vị trí 1).
  • accoonoj → ccoonoj (xóa a tại vị trí 1).
  • ccoonoj → coonoj (xóa c tại vị trí 1).
  • coonoj → clonoj (thay o tại vị trí 2 thành l).
  • clonoj → clunoj (thay o tại vị trí 3 thành u).
  • clunoj → clueoj (thay n tại vị trí 4 thành e).

Cho một chuỗi ký tự ~s~ chỉ gồm các chữ cái Latin (hoa hoặc thường).

Hãy tìm độ dài của chuỗi con đối xứng dài nhất có thể trích từ xâu ~s~ ra.

Yêu cầu: Hãy tìm độ dài lớn nhất của một chuỗi con đối xứng có thể trích ra từ chuỗi ~s~ đã cho.

Input

Một chuỗi dòng ký tự ~s~ (~1 \leq |s| \leq 2000~).

Output

In ra một số nguyên duy nhất — độ dài chuỗi con đối xứng dài nhất của ~s~.

Example input 1

bbbbab

Example output 1

4

Note 1

• Chuỗi con đối xứng dài nhất là bbbb, độ dài ~4~.

Cho ba chuỗi ~s_1,s_2,s_3~.

Hãy kiểm tra xem ~s_3~ có thể được tạo thành bằng cách xen kẽ các ký tự của chuỗi ~s_1~ và chuỗi ~s_2~ hay không, vẫn giữ nguyên thứ tự tương đối của các ký tự trong mỗi chuỗi.

Yêu cầu: Kiểm tra xem chuỗi ~s_3~ có thể được tạo thành bằng cách xen kẽ các ký tự của hai chuỗi ~s_1~ và ~s_2~ (vẫn giữ nguyên thứ tự tương đối của mỗi chuỗi) hay không.

Input

Chuỗi ~s_1,s_2,s_3~ trên một dòng (~1 \leq |s_1|,|s_2| \leq 1000,1 \leq |s_3| \leq 2000~).

Output

In ra YES nếu ~s_3~ có thể tạo bằng cách xen kẽ các ký tự của ~s_1~ và ~s_2~.

Example input 1

aab
axy
aaxaby

Example output 1

YES

Note 1

~s_1~ = aab. ~s_2~ = axy.

Xen kẽ: aaxaby.

→ Đúng.

Cho một lưới có kích thước ~m*n~, mỗi ô trong lưới chứa một giá trị nguyên ~a[i][j]~. Bạn bắt đầu từ ô ~(1,1)~ và muốn đi đến ô ~(m,n)~. Mỗi lần, bạn chỉ được đi sang phải hoặc đi xuống. Hãy tìm tổng giá trị lớn nhất có thể đặt được trên một đường đi hợp lệ.

Yêu cầu: Tính tổng giá trị lớn nhất của các ô trên đường đi từ ~(1,1)~ đến ~(m,n)~, chỉ được đi sang phải hoặc đi xuống.

Input

• Dòng đầu chứa hai số nguyên dương ~m,n~ (~1 \leq m,n \leq 1000~), là kích thước của lưới.
• ~m~ dòng tiếp theo, mỗi dòng chứa ~n~ số nguyên ~a[i][j]~ (~|a[i][j]| \leq 10^6~), là giá trị tại ô đó.

Output

Một số nguyên duy nhất, là tổng giá trị lớn nhất có thể đạt được.

Example input 1

3 3
1 2 3
4 5 6
7 8 9

Example output 1

29

Note 1

• Đường đi tối ưu: ~(1,1)~ → ~(2,1)~ → ~(3,1)~ → ~(3,2)~ → ~(3,3)~. Tổng: ~1 + 4 + 7 + 8 + 9 = 29~.

Một thanh sắt có độ dài ~l~ có thể được cắt thành các đoạn nhỏ hơn.

Cho bảng giá gồm ~l~ số nguyên dương ~p_1,p_2,...,p_l~, trong đó ~p_i~ là giá bán của một đoạn sắt có độ dài ~i~.

Bạn có thể cắt hoặc không cắt thanh sắt, và có thể sử dụng lại cùng một độ dài nhiều lần (tức là có thể cắt ra nhiều đoạn cùng độ dài).

Yêu cầu: Hãy xác định cách cắt thanh sắt sao cho tổng giá trị thu được là lớn nhất.

Input

• Dòng thứ nhất: một số nguyên dương ~l~ (~1 \leq l \leq 10^6~).
• Dòng thứ hai: gồm ~l~ số nguyên dương ~p_1,p_2,...,p_l~ (~1 \leq p_i \leq l~).

Output

Một số nguyên duy nhất — giá trị thu được lớn nhất khi cắt thanh sắt tối ưu.

Example input 1

5
2 5 7 3 9

Example output 1

12

Note 1

• Có thể cắt thanh sắt dài 5 thành các đoạn dài 2 và 3, thu được tổng giá ~p_2+p_3 = 5+7=12~, là lớn nhất.

Một dãy ngoặc đúng nếu nó được tạo bởi các ký tự ( và ) và tuân thủ quy tắc sau:

• Mỗi dấu ( phải có một dấu ngoặc ) tương ứng đi sau nó.
• Không có vị trí nào dãy mà số ngoặc ) vượt quá số ngoặc ) tính đến vị trí đó.

Cho ~n~ số nguyên dương, hãy đếm xem số lượng dãy ngoặc đúng có độ dài ~2n~ (tức là gồm ~n~ cặp ngoặc).

Yêu cầu:Tính và in ra số lượng dãy ngoặc đúng có độ dài ~2n~.

Input

Một dòng duy nhất chứa số nguyên dương ~n~ - số cặp ngoặc (~1 \leq n \leq 1000~).

Output

Một dòng duy nhất chứa số lượng dãy ngoặc đúng độ dài ~2n~ modulo ~10^9+7~.

Example input 1

3

Example output 1

5

Note 1

• Có 5 dãy ngoặc đúng có độ dài 6: ((())), (()()), (())(), ()(()), ()()().

Có ~n~ hòn đá được xếp thành một hàng, hòn đá thứ ~i~ có độ cao là ~h_i~. Một con ếch đang đứng ở hòn đá ~1~ và muốn nhảy đến hòn đá ~n~.

Từ hòn đá thứ ~i~, ếch có thể nhảy đến: hòn đá ~i+1~ hoặc hòn đá ~i+2~ (nếu tồn tại). Chi phí cho một lần nhảy từ hòn đó ~i~ sang ~j~ là ~|h_i-h_j|~.

Hãy tính tổng chi phí nhỏ nhất để ếch có thể nhảy từ hòn đá ~1~ đến hòn đá ~n~.

Yêu cầu:Tìm chi phí tối thiểu để con ếch nhảy từ hòn đá đầu tiên đến hòn đá cuối cùng.

Input

• Dòng thứ nhất: số nguyên dương ~n~ - số lượng hòn đá (~1 \leq n \leq 10^5~).
• Dòng thứ hai: ~n~ số nguyên dương ~h_1,h_2,...,h_n~ - độ cao của các hòn đá (~1 \leq h_i \leq 10^9~).

Output

Một số nguyên duy nhất — chi phí nhỏ nhất mà ếch phải bỏ ra để nhảy đến hòn đá cuối cùng.

Example input 1

4
10 30 40 20

Example output 1

30

Note 1

• Đường đi tối ưu:
  • Nhảy từ ~1~ → ~2~: chi phí ~= |10-30|=20~.
  • Nhảy từ ~2~ → ~4~: chi phí ~= |30-20|=10~. Tổng chi phí là ~20+10=30~.

Bạn có vô số viên gạch domino kích thước ~2*1~. Hỏi có bao nhiêu cách để lát kín một sàn nhà hình chữ nhật kích thước ~2*n~ bằng các viên gạch domino ~2*1~.

Yêu cầu: Tính và in ra số cách để lát kín một sàn nhà kích thước ~2*n~ bằng các viên gạch ~2*1~.

Input

Một số nguyên dương ~n~ - chiều dài của sàn (~1 \leq n \leq 10^6~).

Output

Một số nguyên - số cách lát kín modulo ~10^9~.

Example input 1

10

Example output 1

89

Cho số nguyên dương ~n~.

Mỗi bước, bạn có thể thực hiện một trong ba thao tác sau:

• Trừ ~1~.
• Chia cho ~2~ (nếu ~n~ chia hết cho ~2~).
• Chia cho ~3~ (nếu ~n~ chia hết cho ~3~).

Yêu cầu: Tính và in ra số bước tối thiểu cần thực hiện để biến ~n~ thành ~1~ bằng các thao tác đã cho.

Input

Một số nguyên dương ~n~ (~1 \leq n \leq 10^6~).

Output

Một số nguyên - là số bước ít nhất cần để đưa ~n~ về ~1~.

Example input 1

10

Example output 1

3

Note 1

• Các bước tối ưu: ~10 → 9 → 3 → 1~ (3 bước).

Cho một lưới kích thước ~m*n~, mỗi ô chứa một ký tự chữ cái (viết thường hoặc viết hoa).

Bạn cần đếm số đường đi từ ô ~(1, 1)~ đến ô ~(m, n)~ sao cho mỗi bước chỉ được đi sang phải hoặc đi xuống.

Chuỗi ký tự tạo thành trên đường đi là một chuỗi Palindrome (đọc xuôi hay ngược đều giống nhau).

Yêu cầu: Tính số lượng đường đi từ ~(1, 1)~ đến ~(m, n)~ sao cho chuỗi ký tự thu được là palindrome. Kết quả có thể rất lớn, hãy in ra kết quả modulo 10⁹ + 7.

Input

• Dòng đầu chứa hai số nguyên ~m,n~ - kích thước của lưới.
• ~m~ dòng tiếp theo, mỗi dòng gồm ~n~ ký tự (không có khoảng trắng), biểu diễn các ký tự trong từng ô của lưới.

Output

Một số nguyên duy nhất - là số đường đi từ ~(1, 1)~ đến ~(m,n)~ tạo thành chuỗi palindrome, lấy mod ~10^9+7~.

Scoring

• Subtask 1 ~(30\%)~: ~m, n \leq 10~.
• Subtask 2 ~(70\%)~: ~m, n \leq 100~.

Example input 1

2 3
aba
aaa

Example output 1

1

Note 1

• Ba đường đi tạo thành palindrome là:
  • ~(1, 1)~ → ~(1, 2)~ → ~(1, 3)~ → ~(2, 3)~: abaa (không đối xứng).
  • ~(1, 1)~ → ~(2, 1)~ → ~(2, 2)~ → ~(2, 3)~: aaaa (đối xứng).

→ Có ~3~ đường hợp lệ.

Cho ba chuỗi ký tự ~s_1,s_2,s_3~.

Hãy tìm độ dài của dãy con chung dài nhất xuất hiện đồng thời trong cả ba chuỗi.

Nhiệm vụ là tìm độ dài lớn nhất của dãy ký tự xuất hiện trong cả 3 chuỗi theo định nghĩa trên.

Yêu cầu: Tính độ dài của dãy con chung dài nhất của cả ba chuỗi ~s_1,s_2,s_3~.

Input

• Dòng thứ nhất: chuỗi ~s_1~.
• Dòng thứ hai: chuỗi ~s_2~.
• Dòng thứ ba: chuỗi ~s_3~.

Lưu ý: Các chuỗi chỉ gồm ký tự chữ cái hoặc chữ số, không có khoảng trắng.

Output

Một số nguyên duy nhất - là độ dài dãy con chung dài nhất của cả ba chuỗi.

Scoring

• Subtask ~1~ ~(30\%)~: ~|s_1|,|s_2|,|s_3| \leq 50~.
• Subtask ~2~ ~(70\%)~: ~|s_1|,|s_2|,|s_3| \leq 200~.

Example input 1

abcde
ace
aecde

Example output 1

3

Note 1

• Dãy con chung dài nhất là ace, có độ dài ~3~.