Một tấm kính hình chữ nhật gồm ~n~ hàng và ~m~ cột. Mỗi ô có một trong hai màu:

• ~0~: kính trong;
• ~1~: kính sẫm màu.

Người thợ có thể thực hiện các đường cắt theo ranh giới giữa hai hàng liên tiếp hoặc hai cột liên tiếp.

• Một đường cắt dọc đi từ mép trên đến mép dưới của tấm kính.
• Một đường cắt ngang đi từ mép trái đến mép phải của tấm kính.

Sau khi cắt, tấm kính được chia thành các mảnh hình chữ nhật.

Yêu cầu

Tìm số đường cắt ít nhất cần thực hiện để mỗi mảnh thu được chỉ chứa đúng một màu.

Dữ liệu

Dữ liệu vào gồm:

• Dòng đầu chứa hai số nguyên ~n, m~ ~(1 \le n, m \le 200)~.
• ~n~ dòng tiếp theo, mỗi dòng gồm ~m~ ký tự ~0~ hoặc ~1~, mô tả tấm kính.

Kết quả

In ra một số nguyên duy nhất là số đường cắt ít nhất cần thực hiện.

Ví dụ

Ví dụ 1

Input

4 7
0000000
0111000
0111100
0000000

Output

6

Ví dụ 2

Input

4 5
00000
01100
01100
00000

Output

4

Ví dụ 3

Input

4 4
0101
1010
0101
1010

Output

6

Giải thích

Ví dụ 2

Cần cắt giữa hàng ~1~ và hàng ~2~, giữa hàng ~3~ và hàng ~4~, giữa cột ~1~ và cột ~2~, giữa cột ~3~ và cột ~4~.

Ví dụ 3

Cần cắt giữa mọi cặp hàng liên tiếp và mọi cặp cột liên tiếp, tổng cộng ~6~ đường cắt.

Ràng buộc và chấm điểm

Ràng buộc

~1 \le n, m \le 200~.

Chấm điểm

• Subtask~1~ ~(5\%)~: tấm kính có dạng bàn cờ, ô ~(i,j)~ mang màu ~0~ khi ~i+j~ chẵn và mang màu ~1~ khi ~i+j~ lẻ.
• Subtask~2~ ~(11\%)~: ~n=1~.
• Subtask~3~ ~(11\%)~: có đúng một ô mang màu ~1~.
• Subtask~4~ ~(23\%)~: không có ràng buộc bổ sung.

Một trạm điều phối có ~N~ đơn vị năng lượng và phải phân bổ toàn bộ số năng lượng này.

Trước hết, trạm chọn một số nguyên không âm ~k~ ~(0 \le k \le N)~ làm năng lượng dự phòng. Phần còn lại gồm ~N-k~ đơn vị được cấp cho hai robot giống nhau trong ~d~ lượt sạc.

Trạm cũng có thể không cấp năng lượng cho hai robot. Trường hợp này chỉ xảy ra khi ~k=N~ và ~d=0~.

Nếu có sạc, trong mỗi lượt, hai robot phải nhận cùng một lượng năng lượng. Cụ thể, nếu robot thứ nhất nhận ~x~ đơn vị thì robot thứ hai cũng nhận ~x~ đơn vị, trong đó ~x~ là số nguyên dương.

Hai phương án phân bổ được xem là khác nhau nếu có ít nhất một trong các điều sau:

• giá trị ~k~ khác nhau;
• số lượt ~d~ khác nhau;
• tồn tại một lượt mà lượng năng lượng cấp cho mỗi robot khác nhau.

Yêu cầu

Tính số phương án phân bổ năng lượng khác nhau. Vì kết quả có thể rất lớn, hãy in phần dư của kết quả khi chia cho ~10^9+7~.

Dữ liệu

Dữ liệu vào gồm một số nguyên ~N~.

Kết quả

In ra một số nguyên duy nhất là số phương án phân bổ năng lượng khác nhau modulo ~10^9+7~.

Ví dụ

Ví dụ 1

Input

4

Output

4

Ví dụ 2

Input

5

Output

4

Ví dụ 3

Input

793

Output

137435472

Giải thích

Ví dụ 1

Xét các giá trị có thể của ~k~:

• ~k=4~: trạm giữ toàn bộ năng lượng dự phòng, hai robot không nhận gì. Có ~1~ phương án.
• ~k=2~: còn ~2~ đơn vị, chỉ có ~d=1~, mỗi robot nhận ~1~ đơn vị.

• ~k=0~: còn ~4~ đơn vị, có ~2~ phương án:

  • ~d=1~, mỗi robot nhận ~2~ đơn vị;
  • ~d=2~, mỗi lượt mỗi robot nhận ~1~ đơn vị.
• ~k=1~ và ~k=3~: không thể chia phần còn lại cho hai robot theo yêu cầu.

Tổng cộng có ~1+1+2=4~ phương án.

Ràng buộc và chấm điểm

Ràng buộc

~1 \le N \le 10^{18}~.

Chấm điểm

• Subtask~1~ ~(12\%)~: ~N \le 10~.
• Subtask~2~ ~(17\%)~: ~N \le 1000~.
• Subtask~3~ ~(36\%)~: ~N \le 10^6~.
• Subtask~4~ ~(5\%)~: không có ràng buộc bổ sung.

Một khu thử nghiệm được chia thành lưới ~n \times m~. Mỗi ô có một trong ba trạng thái:

• ~2~: đã có một trạm đo bền vững được lắp đặt. Trạm này vẫn hoạt động bình thường dù có thiết bị ở ô kề cạnh.
• ~1~: ô bị khóa, không được lắp thêm thiết bị.
• ~0~: ô trống, có thể lắp một cảm biến nhạy.

Người quản lý được chọn một số ô ~0~ để lắp cảm biến nhạy.

Một cảm biến nhạy bị nhiễu nếu có ít nhất một thiết bị đang hoạt động ở ô kề cạnh theo một trong bốn hướng: trên, dưới, trái, phải. Thiết bị gây nhiễu có thể là một trạm đo bền vững hoặc một cảm biến nhạy khác.

Các trạm đo bền vững không bị ảnh hưởng bởi quy tắc này; vì vậy hai trạm ~2~ vẫn có thể nằm cạnh nhau.

Yêu cầu

Tìm số thiết bị hoạt động lớn nhất có thể có trong khu thử nghiệm, tính cả các trạm ~2~ đã có và các cảm biến nhạy được chọn thêm, sao cho không cảm biến nhạy nào bị nhiễu.

Dữ liệu

Dữ liệu vào gồm:

• Dòng đầu chứa hai số nguyên ~n, m~ ~(1 \le n, m \le 80)~.
• ~n~ dòng tiếp theo, mỗi dòng gồm ~m~ ký tự ~0~, ~1~ hoặc ~2~, mô tả khu thử nghiệm.

Kết quả

In ra một số nguyên duy nhất là số thiết bị hoạt động lớn nhất có thể có.

Ví dụ

Ví dụ 1

Input

4 4
0100
0202
1000
2120

Output

6

Ví dụ 2

Input

4 4
0000
0000
0000
0000

Output

8

Giải thích

Ví dụ 2

Có thể lắp cảm biến theo dạng bàn cờ. Khi đó có ~8~ cảm biến và không có hai cảm biến nào kề cạnh.

Ràng buộc và chấm điểm

Ràng buộc

~1 \le n, m \le 80~.

Chấm điểm

• Subtask~1~ ~(8\%)~: ~n,m \le 4~.
• Subtask~2~ ~(15\%)~: mọi ô đều là ~0~.
• Subtask~3~ ~(16\%)~: ~n=2~.
• Subtask~4~ ~(52\%)~: ~n \le 15~.
• Subtask~5~ ~(19\%)~: không có ràng buộc bổ sung.

Một mạng lưới vận chuyển gồm ~n~ trạm, được nối với nhau thành một cây có gốc tại trạm ~1~.

Mỗi tuyến bay luôn đi từ trạm có số hiệu nhỏ hơn đến trạm có số hiệu lớn hơn. Với mỗi trạm ~i>1~, biết trạm cha ~p_i~ ~(p_i<i)~. Tuyến bay đi từ ~p_i~ đến ~i~ được gọi là tuyến ~i~.</p>

Trong ngày, một thiết bị bay đã đi qua mỗi tuyến đúng một lần và ghi lại:

• chỉ số tín hiệu ~z_i~;
• độ biến thiên luồng khí ~b_i~, có thể âm.

Cuối ngày, thiết bị thực hiện thêm đúng một hành trình gồm không quá ~k~ tuyến liên tiếp trên một đường đi có hướng từ tổ tiên xuống hậu duệ.

Với một hành trình đã chọn, gọi:

• ~z_{\text{first}}~ là chỉ số tín hiệu của tuyến đầu tiên;
• ~z_{\text{last}}~ là chỉ số tín hiệu của tuyến cuối cùng;
• ~b_i~ là các giá trị độ biến thiên luồng khí trên toàn bộ hành trình.

Điểm của hành trình được tính bởi:

~z_{\text{last}}\left(z_{\text{last}}+\sum b_i\right)+z_{\text{first}}^2~.

Khi hành trình chỉ gồm một tuyến, tuyến đầu tiên cũng chính là tuyến cuối cùng và công thức trên vẫn được áp dụng.

Yêu cầu

Tìm điểm hành trình lớn nhất có thể đạt được.

Dữ liệu

Dữ liệu vào gồm:

• Dòng đầu chứa hai số nguyên ~n, k~ ~(1 \le k \le n \le 3\cdot 10^5)~.
• Dòng thứ hai chứa ~n-1~ số nguyên. Số thứ ~i~ là cha của trạm ~i+1~, tức là ~p_{i+1}~ ~(1 \le p_{i+1} \le i)~.
• Dòng thứ ba chứa ~n-1~ số nguyên. Số thứ ~i~ là ~z_{i+1}~ ~(1 \le z_{i+1} \le 10^5)~.
• Dòng thứ tư chứa ~n-1~ số nguyên. Số thứ ~i~ là ~b_{i+1}~ ~(-10^5 \le b_{i+1} \le 10^5)~.

Kết quả

In ra một số nguyên duy nhất là điểm hành trình lớn nhất có thể đạt được.

Ví dụ

Ví dụ 1

Input

5 1
1 2 2 1
5 4 8 7
6 3 9 3

Output

200

Ví dụ 2

Input

9 2
1 2 1 1 4 3 6 5
1 3 7 8 4 1 8 2
1 -7 -1 -6 3 8 -1 6

Output

120

Giải thích

Ví dụ 1

Vì ~k=1~, ta chỉ xét từng tuyến riêng lẻ. Điểm của bốn tuyến lần lượt là ~80~, ~44~, ~200~ và ~119~. Giá trị lớn nhất là ~200~.

Ràng buộc và chấm điểm

Ràng buộc

~1 \le k \le n \le 3\cdot 10^5~.

Với mọi ~2 \le i \le n~:

• ~1 \le p_i < i~;
• ~1 \le z_i \le 10^5~;
• ~-10^5 \le b_i \le 10^5~.

Chấm điểm

• Subtask~1~ ~(14\%)~: ~n \le 1000~.
• Subtask~2~ ~(23\%)~: với mọi ~2 \le i \le n~, ~z_i=1~ và ~b_i>1~.
• Subtask~3~ ~(35\%)~: ~n \le 50000~.
• Subtask~4~ ~(38\%)~: không có ràng buộc bổ sung.

Một khu vườn được chia thành lưới ~n \times m~. Ô ở hàng ~i~, cột ~j~ được ký hiệu là ~a_{i,j}~.

• Nếu ~a_{i,j}=0~, ô đất đang trống.
• Nếu ~a_{i,j}>0~, tại ô đó đã có một cây cao ~a_{i,j}~.

Người làm vườn có ~k~ cây non, với chiều cao lần lượt là ~h_1,h_2,\ldots,h_k~. Mỗi cây non phải được trồng vào một ô đất trống và không có hai cây nào cùng một ô.

Các cây non phải được trồng vào ~k~ ô liên tiếp trên cùng một hàng. Cụ thể, người làm vườn chọn một hàng ~i~ và một cột bắt đầu ~j~, rồi sử dụng các ô:

~a_{i,j},a_{i,j+1},\ldots,a_{i,j+k-1}~.

Có thể sắp xếp ~k~ cây non vào các ô này theo bất kỳ thứ tự nào.

Một cây non tại cột ~c~ nhận đủ ánh sáng nếu mọi cây đã có ở phía trước nó, tức là ở các hàng có chỉ số nhỏ hơn trong cùng cột ~c~, đều thấp hơn nghiêm ngặt so với cây non đó.

Một đoạn gồm ~k~ ô liên tiếp được gọi là phù hợp nếu:

• cả ~k~ ô đều đang trống;
• có thể hoán vị các cây non để mỗi cây đều nhận đủ ánh sáng.

Yêu cầu

Đếm số đoạn phù hợp.

Dữ liệu

Dữ liệu vào gồm:

• Dòng đầu chứa ba số nguyên ~n, m, k~ ~(1 \le n,m \le 2000, 1 \le k \le m)~.
• Dòng thứ hai chứa ~k~ số nguyên ~h_1,h_2,\ldots,h_k~, là chiều cao các cây non.

• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số nguyên mô tả khu vườn:

  • ~a_{i,j}=0~ nếu ô đất trống;
  • ~1 \le a_{i,j} \le 10^9~ nếu ô đã có cây.

Kết quả

In ra một số nguyên duy nhất là số đoạn phù hợp.

Ví dụ

Ví dụ 1

Input

3 4 2
2 6
0 0 3 1
8 0 0 0
0 0 1 0

Output

3

Ví dụ 2

Input

2 4 4
5 2 4 3
1 2 3 4
0 0 0 0

Output

1

Ví dụ 3

Input

5 5 3
17 3 17
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

Output

15

Giải thích

Ví dụ 1

Ba đoạn phù hợp là:

• hai ô đầu tiên của hàng ~1~;
• các ô từ cột ~2~ đến cột ~3~ của hàng ~2~;
• các ô từ cột ~3~ đến cột ~4~ của hàng ~2~.

Ví dụ 2

Bốn cây non có thể được trồng vào bốn ô trống nếu sắp xếp chúng phù hợp với yêu cầu của từng cột.

Ví dụ 3

Không có cây nào đã được trồng trong vườn, nên mọi đoạn dài ~3~ đều phù hợp. Có tổng cộng ~5\cdot 3=15~ đoạn.

Ràng buộc và chấm điểm

Ràng buộc

~1 \le n,m \le 2000~, ~1 \le k \le m~.

Với mọi ~1 \le t \le k~:

• ~1 \le h_t \le 10^9~.

Với mọi ~1 \le i \le n~, ~1 \le j \le m~:

• ~a_{i,j}=0~ hoặc ~1 \le a_{i,j} \le 10^9~.

Chấm điểm

• Subtask~1~ ~(11\%)~: ~k \le 2~.
• Subtask~2~ ~(13\%)~: ~n,m \le 200~.
• Subtask~3~ ~(29\%)~: ~n,m \le 500~.
• Subtask~4~ ~(57\%)~: không có ràng buộc bổ sung.