Bạn An có một dãy số gồm ~N~ phần tử nguyên dương ~a_1~, ~a_2~, ..., ~a_N~ . An muốn tính tổng các số trong dãy. Vấn đề ở đây là chiếc máy tính của An khá chậm nên cậu ta muốn tìm cách tính tổng các số nguyên dương trong dãy sao cho thời gian máy tính hoạt động nhỏ nhất có thể. Cụ thể:

• Chỉ có thể cộng hai phần tử liên tiếp;

• Sau khi cộng hai phần tử liên tiếp, hai phần tử sẽ bị xoá khỏi dãy và phần tử mới bằng tổng hai phần tử sẽ được thêm vào vị trí xoá, vị trí tương đối giữa các phần tử trong dãy mới giữ nguyên;

• Thời gian để tính tổng hai số nguyên dương ~x~ và ~y~ là ~(x + y)^2~.

Yêu cầu: Bạn hãy đưa ra thời gian ít nhất để máy tính có thể tính được tổng cả dãy số mà An muốn tính.

Input

Dòng đầu tiên gồm một số nguyên dương ~N~ (~N \le 3000~) — độ dài dãy số.

Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, \cdots, a_N~ (~a_i \le 10^4~) — dãy ~a~.

Output

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

Scoring

Sample Input 1

3
3 4 5

Sample Output 1

193

Notes

• Tính ~3 + 4 = 7~ với thời gian ~(3 + 4)^2 = 49~;

• Tính ~7 + 5 = 12~ với thời gian ~(7 + 5)^2 = 144~;

• Như vậy tổng thời gian máy tính phải thực hiện là ~49 + 144 = 193~.

Cho số nguyên ~N~ và một dãy số nguyên ~a_1, a_2, \dots, a_N~. Nhiệm vụ của bạn là phải cắt dãy số trên thành một số dãy số (giữ nguyên thứ tự) thỏa mãn:

• Tổng của mỗi dãy số không lớn hơn số nguyên ~M~.

• Tổng của các số lớn nhất trong các dãy trên là nhỏ nhất.

Input

Dòng đầu gồm ~2~ số nguyên ~N~ và ~M~. ~(1 \le N \le 10^5, M \le 2^{63})~

Dòng thứ hai gồm ~N~ số nguyên của dãy ~a_1, a_2, \dots, a_N~. ~(0 \le a_i \le 10^6)~

Output

Gồm một số duy nhất là tổng của các số lớn nhất trong các dãy số trên. Nếu không có cách cắt nào thỏa mãn hai điều kiện trên, in ra ~-1~.

Sample Input 1

8 17
2 2 2 8 1 8 2 1

Sample Output 1

12

Notes

Giải thích: Cắt thành ~3~ dãy ~222, 818, 21~

Đối với Mirko, không có hạnh phúc nào lớn hơn việc tìm thấy một cuộn băng dính mới, và ngày hôm nay anh ấy đặc biệt hạnh phúc vì anh ấy còn tìm thêm được cuốn lịch Advent của Slavko.

Cuốn lịch Advent có thể biểu diễn như một bảng hình chữ nhật với ~n~ hàng và ~m~ cột, mỗi ô vuông chứa một cửa sổ nhỏ, và đằng sau mỗi cửa sổ là một miếng sô cô la. Slavko đã mở một số ô trong số đó, còn những cửa sổ khác vẫn đang đóng.

Mirko quyết định sử dụng cuộn băng dính của anh ấy để dán lại tất cả những cửa sổ đóng. Cuộn băng dính thì dài vô tận, và nó có chiều rộng bằng ~1~ ô của cuốn lịch. Mirko có thể xé một đoạn băng dính và dùng nó để dán một đoạn liền kề những ô cửa sổ đã đóng theo chiều dọc hoặc chiều ngang. Anh ấy không muốn dán nhiều hơn một lớp băng dính lên bất kì cửa sổ nào, vì anh ấy vẫn muốn giữ tình bạn với Slavko.

Anh ấy đang tự hỏi rằng, anh ấy cần tối thiểu bao nhiêu mẩu băng dính để dán lại hết các cửa sổ đóng trong cuốn lịch.

Input

Dòng dầu tiên chứa ~2~ số nguyên ~n~ và ~m~ ~(1 \le n \le 1000, 1 \le m \le 10)~, các kích thước của cuốn lịch Advent.

Mỗi dòng trong số ~n~ dòng sau chứa ~m~ kí tự . và # , biểu diễn cuốn lịch Advent.

Kí tự . mô tả một ô cửa sổ mở, và kí tự # biểu diễn một ô cửa sổ đóng

Output

In ra số lượng nhỏ nhất các mẩu băng dính cần thiết để dán hết những ô cửa sổ đóng

Sample 1

Input

2 3
#.#
###

Output

3

Sample 2

Input

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

Output

3

Sample 3

Input

4 4
####
#.#.
#.##
####

Output

5

Giải thích test ví dụ đầu tiên

Một giải pháp có thể đưa ra là sử dụng một đoạn băng dính cho cột đầu tiên, một đoạn cho cột thứ ~3~ và một đoạn cho ô cửa sổ ở hàng thứ ~2~ và cột thứ ~2~

Subtask

Có ~10~ test thỏa mãn: mỗi ô cửa sổ đóng liền kề với tối đa ~2~ ô cửa sổ đóng khác

Có ~8~ test thỏa mãn: ~1 \le n \le 10~

Có ~10~ test còn lại: không có ràng buộc gì thêm

Có ~n~ học sinh trong một lớp đang làm việc theo nhóm. Các học sinh sẽ chia thành các nhóm (một số học sinh có thể làm việc một mình) để làm việc và sau đó cùng nhau thảo luận kết quả. Học sinh thứ ~i~ mất ~a_i~ phút để hoàn thành phần việc của mình.

Nếu học sinh làm việc với tốc độ khác nhau, điều đó có thể gây khó chịu cho các học sinh giỏi và áp lực cho các bạn học sinh kém hơn. Độ lệch của một nhóm được định nghĩa là giá trị lớn nhất ~a_i~ trong nhóm trừ đi giá trị nhỏ nhất ~a_i~ trong nhóm. Lưu ý rằng nhóm chỉ có một học sinh sẽ có độ lệch bằng ~0~. Hỏi có bao nhiêu cách để chia các học sinh thành các nhóm sao cho tổng độ lệch của tất cả các nhóm không vượt quá ~k~?

Hai cách chia được coi là khác nhau nếu tồn tại một cặp học sinh cùng nhóm trong một cách chia và khác nhóm trong cách chia còn lại.

Input

Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách ~n~ và ~k~ (~1 \le n \le 200~, ~0 \le k \le 1000~) — số lượng học sinh và tổng độ lệch tối đa cho phép.

Dòng thứ hai chứa ~n~ số nguyên ~a_i~ (~1 \le a_i \le 500~) — thời gian học sinh thứ ~i~ cần để hoàn thành phần việc của mình.

Output

In ra một số nguyên — số cách để chia nhóm các học sinh. Vì kết quả có thể rất lớn, hãy in ra kết quả modulo ~10^9 + 7~.

Sample Input 1

3 2
2 4 5

Sample Output 1

3

Sample Input 2

4 3
7 8 9 10

Sample Output 2

13

Sample Input 3

4 0
5 10 20 21

Sample Output 3

1

Notes

Trong ví dụ đầu tiên, ta có ba cách chia:

• Học sinh thứ nhất và thứ hai tạo thành một nhóm, học sinh thứ ba tạo thành một nhóm riêng. Tổng độ lệch là ~2 + 0 = 2~.

• Học sinh thứ nhất tạo thành một nhóm, học sinh thứ hai và thứ ba tạo thành một nhóm. Tổng độ lệch là ~0 + 1 = 1~.

• Cả ba học sinh đều làm việc một mình. Tổng độ lệch là ~0~.

Trong ví dụ thứ ba, tổng độ lệch phải bằng ~0~, vì vậy mỗi học sinh phải làm việc một mình.

Cho số nguyên ~N~ và mảng ~a_1, a_2, \ldots, a_n~. Điểm của một đoạn liên tiếp bằng tổng giá trị lớn nhất và giá trị bé nhất trong đoạn. Cắt mảng đã cho thành ~K~ đoạn liên tiếp không giao nhau, không rỗng sao cho tổng điểm của các đoạn là lớn nhất. Mỗi phần tử phải nằm trong chính xác một đoạn.

Input

• Dòng đầu tiên gồm số nguyên ~N~ — Số lượng phần tử của mảng (~1 \leq N \leq 10^5, 1 \leq K \leq \min(N, 20)~).

• Dòng thứ hai gồm ~N~ số nguyên ~a_1, a_2, \ldots, a_n~ – Giá trị của mảng (~0 \leq a_i \leq 10^9, \forall 1 \leq i \leq N~).

Output

Một số nguyên duy nhất là kết quả bài toán.

Scoring

Sample Input 1

5 3
3 5 2 3 4

Sample Output 1

22

Sample Input 2

3 2
10 6 2006

Sample Output 2

4028

Notes

Ở ví dụ 1, ta chia thành 3 đoạn ~[1, 1], [2, 2]~ và ~[3, 5]~. Kết quả của cách chia này là ~3 + 3 + 5 + 5 + 2 + 4 = 22.~

Ở ví dụ 2, ta chia thành 2 đoạn ~[1, 2]~ và ~[3, 3]~. Kết quả của cách chia này là ~10 + 6 + 2006 + 2006 = 4028~.

Peter có một dãy số nguyên ~a_1, a_2, \dots, a_n~. Peter muốn tất cả các số trong dãy trở thành ~h~. Anh ta có thể thực hiện thao tác "cộng một trên đoạn ~[l, r]~": cộng thêm ~1~ vào tất cả các phần tử trong dãy có chỉ số từ ~l~ đến ~r~ (bao gồm cả hai đầu).

Tuy nhiên, Peter không bao giờ chọn bất kỳ phần tử nào làm điểm bắt đầu của đoạn hai lần. Tương tự, Peter cũng không bao giờ chọn bất kỳ phần tử nào làm điểm kết thúc của đoạn hai lần. Nói cách khác, với hai đoạn bất kỳ ~[l_1, r_1]~ và ~[l_2, r_2]~, nếu Peter đã thực hiện thao tác trên hai đoạn này thì các bất đẳng thức sau phải được đồng thời thỏa mãn: ~l_1 \neq l_2~ và ~r_1 \neq r_2~.

Hỏi có bao nhiêu cách khác nhau để biến tất cả các số trong dãy thành ~h~? In ra kết quả này theo modulo ~10^9 + 7~. Hai cách được coi là khác nhau nếu một trong chúng có một đoạn mà cách còn lại không có.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~h~ ~(1 \leq n, h \leq 2000)~.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(0 \leq a_i \leq 2000)~.

Output

In ra một số nguyên duy nhất – đáp án của bài toán theo modulo ~10^9 + 7~.

Sample Input 1

3 2
1 1 1

Sample Output 1

4

Sample Input 2

5 1
1 1 1 1 1

Sample Output 2

1

Sample Input 3

4 3
3 2 1 1

Sample Output 3

0

Cho hai số nguyên ~n~ và ~m~ và một dãy gồm ~n~ số nguyên dương ~a_i~. Đếm số cách xếp ~n~ phần tử vào ~m~ ô trống sao cho: Gọi ~p_i~ là vị trí mà ~i~ được điền, khi đó ~min(|p_i - p_j|) \geq a_i \space (a_i \leq n, j \neq i)~.

In đáp án chia lấy dư cho ~10 ^ 9 + 7~.

Input

Dòng đầu gồm 2 số nguyên dương ~n~ và ~m~.

Dòng thứ hai gồm ~n~ số nguyên dương ~a_i~ (~i \leq n~).

Giới hạn: ~n \leq 50, m \leq 10^6, a_i \leq n~.

Output

Một số duy nhất là kết quả của bài toán chia lấy dư cho ~10 ^ 9 + 7~.

Sample Input 1

2 3
2 2

Sample Output 1

2

Notes

Giải thích test ví dụ: các cách xếp thỏa mãn là "~1 \space o \space 2~", "~2 \space o \space 1~" với ~o~ tượng trưng cho ô trống.

Nam vừa đoạt giải quán quân trong một kỳ thi lập trình danh giá. Ban tổ chức trao thưởng thông qua một trò chơi như sau. Có ~n~ thẻ xếp trên một hàng, được đánh số thứ tự từ ~1~ đến ~n~ từ trái sang phải, trên thẻ thứ ~i~ (~1 \leq i \leq n~) có thông tin:

• Nhãn ~c_i~ là một xâu kí tự gồm các kí tự chữ cái la tinh in hoa (từ ~A~ đến ~Z~);

• Số may mắn ~p_i~ là một số nguyên dương.

Ban tổ chức cũng công bố ~m~ cặp số may mắn và cho phép Nam thực hiện một hoặc nhiều bước chọn các thẻ. Ban đầu, Nam chọn một thẻ bất kì, điểm nhạn được là số may mắn trên thẻ đó. Mỗi bước tiếp theo, Nam thực hiện theo một trong hai cách sau:

1. Trong các thẻ ở phía bên phải thẻ hiện tại, chọn một thẻ có nhãn là một xâu mà có thể nhận được bằng cách xóa từ xâu là nhãn của thẻ hiện tại một số kí tự cuối cùng (ít nhất một kí tự). Số điểm nhận được thêm bằng số may mắn trên thẻ mới chọn;

2. Trong các thẻ ở phía bên phải thẻ hiện tại, chọn một thẻ mà số may mắn trên thẻ này và số may mắn trên thẻ hiện tại là một cặp số may mắn. Cụ thể, nếu số may mắn trên thẻ hiện tại là ~p_i~ và số may mắn trên thẻ mới chọn là ~p_j~ thì cặp số ~(p_i, p_j)~ hoặc ~(p_j, p_i)~ phải là một trong các cặp số may mắn mà Ban tổ chức đã công bố. Số điểm nhận được thêm bằng số may mắn trên thẻ mới chọn.

Sau một số bước chọn, nếu Nam không chọn được nữa thì số tiền thưởng bằng tổng điểm tích lũy được.

Yêu cầu: Hãy giúp Nam tìm cách chọn các thẻ để đạt được tổng số tiền thưởng là lớn nhất.

Input

Vào từ đầu vào chuẩn:

• Dòng thứ nhất chứa số nguyên dương ~n~ và số nguyên không âm ~m~.

• Tiếp theo là ~n~ cặp dòng mô tả thông tin trên thẻ. Cặp dòng thứ ~i~ ~(1 \leq i \leq n)~ có dòng thứ nhất chứa nhãn và dòng thứ hai chứa số may mắn của thẻ thứ ~i~.

• Mỗi dòng trong số ~m~ dòng cuối cùng chứa hai số nguyên dương mô tả một cặp số may mắn.

Các thẻ có thể có nhãn giống nhau và tổng số các kí tự của các nhãn trên các thẻ không vượt quá ~10^6~. Các số may mắn có giá trị không vượt quá ~10^5~. Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra đầu ra chuẩn một số nguyên duy nhất là tổng tiền thưởng lớn nhất chọn được.

Scoring

Sample Input 1

4 1
ABA
5
BC
10
AB
5
A
6
6 10

Sample Output 1

16

Notes

Nam chọn thẻ thứ ~2~ rồi chọn tiếp thẻ thứ ~4~ bằng cách sử dụng cặp số may mắn ~(6, 10)~ để nhận được tổng tiền thưởng là ~16~.

Một cách chọn khác cũng được tổng tiền thưởng là ~16~ bằng cách chọn lần lượt các thẻ ~1, 3, 4~.

Cho hai bảng hai chiều có kích thước lần lượt là ~M \times N~ và ~R \times L~. Bạn cần giải quyết hai bài toán:

• Bài toán ~1~: Điền giá trị ~0~ hoặc ~1~ vào ~M \times N - T~ ô còn trống trên hình chữ nhật kích thước ~M \times N~ (~M, N \leq 16~), trong hình chữ nhật đó có ~T~ ô không được phép điền bất cứ giá trị nào.

• Bài toán ~2~: Điền giá trị ~0~ hoặc ~1~ vào ~W \times H~ ô trống trên hình chữ nhật thứ hai.

Các cách điền sẽ phải thoả mãn điều kiện:

• Nếu ~i+j~ lẻ thì giá trị tại ô ~(i,j)~ không nhỏ hơn các ô không bị cấm chung cạnh với nó.

• Nếu ~i+j~ chẵn thì giá trị tại ô ~(i,j)~ không lớn hơn các ô không bị cấm chung cạnh với nó.

Yêu cầu: Đếm số lượng cách xếp khác nhau của bài toán ~1~ và bài toán ~2~. Hai cách xếp được gọi là khác nhau nếu khi chồng khít ~2~ cách lên nhau (không xoay hoặc lật) có ít nhất một ô khác giá trị.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~M, N, T~ (~M, N \leq 16~), trong đó ~M, N~ là kích thước hình chữ nhật trong bài toán ~1~.

• Dòng tiếp theo chứa số nguyên dương ~T~ (~T \leq M \times N~), là số lượng ô không được điền giá trị trong bảng đầu tiên.

• ~T~ dòng tiếp theo, mỗi dòng chứa một cặp số ~(i, j)~ là toạ độ ô không được điền giá trị trong bảng đầu tiên (~1 \le i \le M~, ~1 \le j \le N~).

• Dòng cuối cùng gồm hai số nguyên dương ~W, H~ (~W \leq 8~, ~H \leq 10^9~) là kích thước hình của bài toán ~2~.

Output

Gồm hai dòng, dòng thứ ~i~ là số cách xếp cho bài toán ~i~ chia lấy dư cho ~10^9+7~.

Scoring

Sample Input 1

5 5
1
3 3
3 10000

Sample Output 1

42240
463482359

Sample Input 2

2 2
1
2 2
2 2

Sample Output 2

5
7

Notes

Xét test ví dụ thứ hai:

• Các cách điền thoả mãn bài toán ~1~:

  

• Các cách điền thoả mãn bài toán ~2~:

  

Gọi ~f(P)~ là số nghịch thế của hoán vị ~P~. Đếm số hoán vị ~P~ thỏa mãn các điều kiện sau:

• ~P~ là một hoán vị của ~\{1, 2, \ldots, n\}~.

• ~f(P) = k~

Input

Một dòng duy nhất chứa hai số nguyên ~n~ ~(1 \leq n \leq 10^5)~ và ~k~ ~(0 \leq k \leq \min\left( \binom{n}{2}, 10^5 \right))~.

Output

In ra một số nguyên duy nhất là số hoán vị có ~k~ nghịch thế. Kết quả chia lấy dư cho ~10^9 + 7~.

Scoring

Sample Input 1

3 2

Sample Output 1

2

Notes

Vì ~n = 3~, chuỗi ban đầu của chúng ta là ~\{1, 2, 3\}~ và chúng ta phải tìm số lượng hoán vị có ~k = 2~ nghịch thế. Có hai hoán vị như vậy:

• ~\{3, 1, 2\}~ có hai nghịch thế, ~(3, 1)~ và ~(3, 2)~.

• ~\{2, 3, 1\}~ có hai nghịch thế, ~(2, 1)~ và ~(3, 1)~.

Vì vậy, đáp án là ~2~.