Mô tả vấn đề

Snuke có một khuôn hình vuông kích thước ~ N \times N ~ ô.

Mỗi cạnh của hình vuông là một phần của chu vi được gắn một lỗ. Nghĩa là, mỗi bên của lưới được có với ~ N ~ lỗ trống, với tổng số ~ 4 \times N ~ lỗ. Các lỗ này được dán nhãn như sau:

• Các lỗ ở phía trên của lưới: ~ U1, U2, ..., UN ~ từ trái sang phải
• Các lỗ ở phía dưới của lưới: ~ D1, D2, ..., DN ~ từ trái sang phải
• Các lỗ ở phía bên trái của lưới: ~ L1, L2, ..., LN ~ từ trên xuống dưới
• Các lỗ ở phía bên phải của lưới: ~ R1, R2, ..., RN ~ từ trên xuống dưới

Hình mô tả nhán đánh dấu các lỗ

Snuke có thể chèn một viên gạch từ mỗi lỗ vào khuôn mà lỗ được gắn vào. Khi một ô bên trong đã bị chiếm, ô đang chiếm sẽ được đẩy sang ô tiếp theo và khi ô tiếp theo cũng bị chiếm bởi một ô khác, ô chiếm đó cũng sẽ được đẩy, v.v. Snuke không thể chèn một ô nếu nó sẽ dẫn đến một ô bị đẩy ra khỏi khuôn. Hành vi của các ô khi một ô được chèn được thể hiện chi tiết tại Đầu vào / Đầu ra Mẫu ~ 1 ~.

Snuke đang cố gắng chèn ~ N \times N ~ viên gạch lần lượt từ các ổ cắm để đạt được trạng thái mà mọi ô vuông đều chứa một viên gạch. Ở đây, anh ta phải chèn chính xác ~ U_i ~ viên gạch từ socket ~ Ui ~, ~ D_i ~ viên gạch từ socket ~ Di ~, ~ L_i ~ viên gạch từ socket ~ Li ~ và ~ R_i ~ viên gạch từ socket ~ Ri ~. Xác định xem có thể chèn các viên gạch mà không vượt quá hạn chế hay không. Nếu có thể, các viên gạch nên được lắp từ các ổ cắm theo thứ tự nào?

Hạn chế

• ~ 1 ≤ N ≤ 300 ~
• ~ U_i, D_i, L_i ~ và ~ R_i ~ là các số nguyên không âm.
• Tổng tất cả các giá trị ~ U_i, D_i, L_i ~ và ~ R_i ~ bằng ~ N \ lần N ~.

Input

Đầu vào được cung cấp từ Đầu vào chuẩn ở định dạng sau:

~ N ~

~ U_1 ~ ~ U_2 ~ ~ ... ~ ~ U_N ~

~ D_1 ~ ~ D_2 ~ ~ ... ~ ~ D_N ~

~ L_1 ~ ~ L_2 ~ ~ ... ~ ~ L_N ~

~ R_1 ~ ~ R_2 ~ ~ ... ~ ~ R_N ~

Output

Nếu có thể chèn các viên gạch sao cho mỗi ô vuông sẽ chứa một viên, hãy in nhãn của các ổ cắm theo thứ tự các ô sẽ được chèn từ chúng, mỗi ô trên một dòng. Nếu không thể, hãy in `NO ''. Nếu tồn tại nhiều hơn một giải pháp, hãy in bất kỳ giải pháp nào trong số đó.

Đầu vào Mẫu 1

3
0 0 1
1 1 0
3 0 1
0 1 1

Đầu ra Mẫu 1

L1
L1
L1
L3
D1
R2
U3
R3
D2

Snuke có thể chèn các ô như trong hình bên dưới. Mũi tên cho biết vị trí được chèn một ô, vòng tròn biểu thị một ô và một số được viết trong một vòng tròn cho biết có bao nhiêu ô được chèn trước đó.

Đầu vào Mẫu 2

2
2 0
2 0
0 0
0 0

Đầu ra mẫu 2

NO

Mạnh đang chơi với thẻ ~ N ~. Thẻ thứ ~ i ~ có một số nguyên ~ X_i ~ trên đó. Mạnh đang cố gắng tạo ra nhiều cặp bài nhất có thể đáp ứng một trong các điều kiện sau:

• Các số nguyên trên hai thẻ giống nhau.
• Tổng các số nguyên trên hai thẻ là bội của ~ M ~.

Tìm số cặp tối đa có thể được tạo ra.

Lưu ý rằng một thẻ không thể được sử dụng trong nhiều cặp.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ (~ 2 ≤ N ≤ 10 ^ 5, 1 ≤ M ≤ 10 ^ 5 ~)

• Dòng thứ hai chứa ~N~ số nguyên ~X_1, X_2,... X_N~ (~1 ≤ X_i ≤ 10 ^ 5~)

Output

In số lượng cặp tối đa có thể được tạo.

Sample Input 1

7 5
3 1 4 1 5 9 2

Sample Output 1

3

Ba cặp ~ (3,2), (1,4) ~ và ~ (1,9) ~ có thể được tạo.

Có thể tạo các cặp ~ (3,2) ~ và ~ (1,1) ~, nhưng số lượng cặp không phải là tối đa với điều này.

Sample Input 2

15 10
1 5 6 10 11 11 11 20 21 25 25 26 99 99 99

Sample Output 2

6

Mô tả vấn đề

Có ~ N ~ ô vuông liên tiếp, được đánh số từ ~ 1 ~ đến ~ N ~ từ trái sang phải. Snuke và Rng đang chơi trò chơi trên bàn cờ bằng cách sử dụng các ô vuông này, được mô tả dưới đây:

1. Đầu tiên, Snuke viết một số nguyên vào mỗi ô vuông.
2. Mỗi người trong hai người chơi sở hữu một mảnh. Snuke đặt quân cờ của mình vào ô vuông ~ 1 ~, và Rng đặt quân cờ vào ô vuông ~ 2 ~.
3. Người chơi có quân cờ ở bên trái đối phương sẽ di chuyển quân cờ của mình. Đích đến phải là một hình vuông ở bên phải của hình vuông nơi quân cờ đang được đặt và không được vào hình vuông nơi quân cờ của đối thủ được đặt.
4. Lặp lại bước 3. Khi các quân cờ không thể di chuyển được nữa, trò chơi kết thúc.
5. Điểm của mỗi người chơi được tính bằng tổng các số nguyên được viết trong các ô vuông mà người chơi đã đặt quân cờ của mình trước khi kết thúc trò chơi.

Snuke đã viết một số nguyên ~ A_i ~ vào hình vuông ~ i (1 ≤ i ≤ N-1) ~, nhưng không viết vào hình vuông thứ ~ N ~. Anh ấy đã quyết định tính toán cho mỗi ~ M ~ số nguyên ~ X_1, X_2, ..., X_M ~, nếu anh ấy viết nó vào ô vuông ~ N ~ và trò chơi được chơi, giá trị Điểm của Snuke - Điểm của Rng sẽ được là bao nhiêu. Ở đây, người ta giả định rằng mỗi người chơi di chuyển quân cờ của mình để tối đa hóa giá trị điểm của người chơi - điểm của đối thủ.

Hạn chế

• ~ 3 ≤ N ≤ 200.000 ~
• ~ 0 ≤ A_i ≤ 10 ^ 6 ~
• Tổng của tất cả ~ A_i ~ nhiều nhất là ~ 10 ^ 6 ~.
• ~ 1 ≤ M ≤ 200.000 ~
• ~ 0 ≤ X_i ≤ 10 ^ 9 ~

Đầu vào

Đầu vào được cung cấp theo định dạng sau:

~ N ~

~ A_1 ~ ~ A_2 ~ ~ ... ~ ~ A_ {N-1} ~

~ M ~

~ X_1 ~

~ X_2 ~

~: ~

~ X_M ~

Đầu ra

Đối với mỗi số nguyên ~ M ~ ~ X_1, ..., X_M ~, in ra giá trị "(Điểm của Snuke) - (Điểm của Rng)" nếu nó được viết thành ô vuông ~ N ~, một trên mỗi dòng.

Đầu vào Mẫu 1

5
2 7 1 8
1
2

Đầu ra Mẫu 1

0

Trò chơi diễn ra như sau, trong đó Sđại diện cho quân của Snuke vàR đại diện cho Rng.

Điểm của cả hai người chơi là ~ 10 ~, do đó "(Điểm của Snuke) - (Điểm của Rng)" là ~ 0 ~.

Đầu vào Mẫu 2

9
2 0 1 6 1 1 2 6
5
2016
1
1
2
6

Đầu ra Mẫu 2

2001
6
6
7
7

Trên một hành tinh xa xôi, có ~M~ ngôn ngữ được sử dụng để giao tiếp, được đánh số từ ~1~ đến ~M~. Vào dịp CODE FESTIVAL được tổ chức trên hành tinh này, ~N~ người tham gia đã tụ họp từ khắp nơi trên hành tinh. Người tham gia thứ ~i~ (~1 ≤ i ≤ N~) có thể nói được ~K_i~ ngôn ngữ là ~L_{i,1}, L_{i,2}, ..., L_{i,K_i}~.

Hai người tham gia ~A~ và ~B~ có thể giao tiếp với nhau nếu và chỉ nếu một trong hai điều kiện sau được thỏa mãn:

• Cả hai cùng nói ít nhất một ngôn ngữ chung.
• Tồn tại một người thứ ba ~X~ mà cả ~A~ và ~B~ đều có thể giao tiếp được với người đó.

Hãy xác định xem tất cả ~N~ người tham gia có thể giao tiếp với nhau (trực tiếp hoặc gián tiếp) hay không.

Input

• Dòng đầu tiên gồm hai số nguyên ~N~ và ~M~ (~2 ≤ N ≤ 10^5, 1 ≤ M ≤ 10^5~) - số người tham gia và số lượng ngôn ngữ khác nhau
• Tiếp theo là ~N~ dòng, dòng thứ ~i~ mô tả người tham gia thứ ~i~. Bắt đầu bằng số nguyên ~K_i~ (~1 ≤ K_i ≤ M~). Tiếp theo là ~K_i~ số nguyên là mã các ngôn ngữ ~L_{i,1} L_{i,2} ... L_{i,K_i}~ là các ngôn ngữ mà người thứ ~i~ có thể giao tiếp.

Bảo đảm rằng các ngôn ngữ trong mỗi dòng là phân biệt. Tổng tất cả các giá trị ~K_i~ không vượt quá ~10^5~.

Output

In ra YES nếu tất cả những người tham gia đều có thể giao tiếp với nhau. Ngược lại, in ra NO.

Sample Input 1

4 6
3 1 2 3
2 4 2
2 4 6
1 6

Sample Output 1

YES

Sample Input 2

4 4
2 1 2
2 1 2
1 3
2 4 3

Sample Output 2

NO

Cho một đồ thị với ~ N ~ đỉnh, được đánh số từ ~ 0 ~ đến ~ N-1 ~. Ban đầu, các cạnh vẫn chưa được thêm vào.

Chúng ta cần xử lý ~ Q ~ truy vấn để thêm các cạnh. Trong truy vấn thứ ~ i ~ ~(1 ≤ i ≤ Q) ~, cho ba số nguyên ~ A_i, B_i ~ và ~ C_i ~ và chúng ta sẽ thêm vô số cạnh vào biểu đồ như sau:

• Hai đỉnh được đánh số ~ A_i ~ và ~ B_i ~ sẽ được nối với nhau bằng một cạnh có trọng số là ~ C_i ~.
• Hai đỉnh được đánh số ~ B_i ~ và ~ A_i + 1 ~ sẽ được nối với nhau bằng một cạnh có trọng số ~ C_i + 1 ~.
• Hai đỉnh được đánh số ~ A_i + 1 ~ và ~ B_i + 1 ~ sẽ được nối với nhau bởi một cạnh có trọng số ~ C_i + 2 ~.
• Hai đỉnh được đánh số ~ B_i + 1 ~ và ~ A_i + 2 ~ sẽ được nối với nhau bằng một cạnh có trọng số ~ C_i + 3 ~.
• Hai đỉnh được đánh số ~ A_i + 2 ~ và ~ B_i + 2 ~ sẽ được nối với nhau bởi một cạnh có trọng số ~ C_i + 4 ~.
• Hai đỉnh được đánh số ~ B_i + 2 ~ và ~ A_i + 3 ~ sẽ được nối với nhau bằng một cạnh có trọng số ~ C_i + 5 ~.
• Hai đỉnh được đánh số ~ A_i + 3 ~ và ~ B_i + 3 ~ sẽ được nối với nhau bằng một cạnh có trọng số ~ C_i + 6 ~.
• ...

Ở đây, hãy xem xét các chỉ số của các đỉnh modulo ~ N ~. Ví dụ, đỉnh được đánh số ~ N ~ là một được đánh số ~ 0 ~, và đỉnh được đánh số ~ 2N-1 ~ là một được đánh số ~ N-1 ~.

Hình dưới đây cho thấy bảy cạnh đầu tiên được thêm vào khi ~ N = 16, A_i = 7, B_i = 14, C_i = 1 ~:

Sau khi xử lý tất cả các truy vấn, bạn hãy tìm tổng trọng số của các cạnh có trong cây khung nhỏ nhất của đồ thị.

Lưu ý rằng có thể có nhiều cạnh nối cùng một cặp đỉnh.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~Q~ (~2 ≤ N ≤ 2 * 10^5, 1 ≤ Q ≤ 2 * 10^5~).
• ~Q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~A_i~ ~B_i~ ~C_i~ (~0 ≤ A_i, B_i ≤ N-1, 1 ≤ C_i ≤ 10 ^ 9~).

Output

In tổng trọng số của các cạnh có trong cây khung nhỏ nhất của đồ thị.

Sample Input 1

7 1
5 2 1

Sample Output 1

21

Sample Input 2

2 1
0 0 1000000000

Sample Output 2

1000000001

Sample Input 3

5 3
0 1 10
0 2 10
0 4 10

Sample Output 3

42

Giải thích

Trong testcase 1, hình dưới đây cho thấy cây khung nhỏ nhất của đồ thị:

Mạnh đang nướng bánh quy. Ban đầu, anh ta có thể nướng một chiếc bánh quy trong một giây. Anh ấy cũng có thể ăn bánh quy do chính mình nướng. Khi còn ~ x ~ bánh quy chưa ăn, anh ta có thể chọn ăn tất cả bánh quy đó. Sau khi anh ta ăn xong những chiếc bánh quy đó, số lượng bánh anh ta có thể nướng mỗi giây trở thành ~ x ~. Lưu ý rằng một chiếc bánh quy luôn cần được nướng trong ~ 1 ~ giây, tức là anh ta không thể nướng một chiếc bánh quy trong ~ 1 / x ~ giây khi ~ x > 1 ~.

Khi anh ta chọn ăn bánh, anh ta phải ăn tất cả chúng, anh ta không thể chọn chỉ ăn một phần của chúng. Anh ta phải mất ~ A ~ giây để ăn bánh quy bất kể số lượng bao nhiêu, trong thời gian đó không có bánh quy nào có thể nướng được.

Anh ấy muốn tặng ~ N ~ bánh quy cho người yêu. Tìm khoảng thời gian ngắn nhất cần thiết để sản xuất ít nhất ~ N ~ bánh quy (chưa ăn) để tặng cho người yêu.

Input

Một dòng duy nhất chứa hai số nguyên ~N~ ~A~ (~1 ≤ N ≤ 10 ^ {12}, 0 ≤ A ≤ 10 ^ {12}~).

Output

In ra thời gian ngắn nhất cần thiết để tạo ra ít nhất ~ N ~ bánh quy chưa ăn.

Sample Input 1

8 1

Sample Output 1

7

Sample Input 2

1000000000000 1000000000000

Sample Output 2

1000000000000

Giải thích

Trong testcase ~1~, có thể tạo ra ~ 8 ~ cookie trong ~ 7 ~ giây, như sau:

• Sau ~ 1 ~ giây: ~ 1 ~ cookie được hoàn thành.
• Sau ~ 2 ~ giây: ~ 1 ~ cookie nữa được hoàn thành, tổng cộng ~ 2 ~. Bây giờ, Mạnh bắt đầu ăn ~ 2 ~ bánh quy đó.
• Sau ~ 3 ~ giây: Anh ấy ăn xong bánh quy và giờ anh ấy có thể nướng ~ 2 ~ bánh quy mỗi giây.
• Sau ~ 4 ~ giây: ~ 2 ~ cookie được hoàn thành.
• Sau ~ 5 ~ giây: ~ 2 ~ cookie nữa được hoàn thành, tổng cộng ~ 4 ~.
• Sau ~ 6 ~ giây: ~ 2 ~ cookie nữa được hoàn thành, tổng cộng ~ 6 ~.
• Sau ~ 7 ~ giây: ~ 2 ~ cookie nữa được hoàn thành, tổng cộng ~ 8 ~.

Mô tả vấn đề

Vấn đề được đặt ra tại CODE FESTIVAL 20XX Finals bao gồm ~ N ~ vấn đề.

Điểm được phân bổ cho vấn đề thứ ~i~ ~ (1 ≤ i ≤ N) ~ là ~ i ~ điểm.

Nam, một thí sinh, đang cố gắng ghi chính xác ~ N ~ điểm. Vì vậy, anh ấy đang quyết định vấn đề nào cần giải quyết.

Vì các bài toán có điểm cao hơn khó hơn, anh ấy muốn giảm thiểu điểm cao nhất của một bài toán trong số các bài do anh ấy giải được.

Xác định tập hợp các vấn đề cần được giải quyết.

Hạn chế

• ~ 1 ≤ N ≤ 10 ^ 7 ~

Input

Đầu vào được cung cấp theo định dạng sau:

~ N ~

Output

Trong số các tập hợp bài toán có tổng điểm là ~ N ~, hãy tìm một tập hợp trong đó điểm cao nhất của một bài toán là nhỏ nhất, sau đó in chỉ số của các bài toán trong tập hợp theo thứ tự bất kỳ, một trên mỗi dòng.

Nếu tồn tại nhiều hơn một bộ như vậy, bất kỳ bộ nào trong số chúng sẽ được chấp nhận.

Đầu vào Mẫu 1

4

Đầu ra Mẫu 1

1
3

Chỉ giải bài toán thứ 4 cũng sẽ dẫn đến tổng điểm là ~ 4 ~ điểm, nhưng giải bài toán thứ 1 và thứ 3 sẽ làm giảm điểm cao nhất của bài toán đã giải.

Đầu vào Mẫu 2

7

Đầu ra Mẫu 2

1
2
4

Tập hợp ~ \\ {3,4 \\} ~ cũng sẽ được chấp nhận.

Đầu vào Mẫu 3

1

Đầu ra mẫu 3

1

Vương quốc H32 Da Poet có ~N~ thị trấn, được đánh số từ ~1~ đến ~N~. Hiện tại, không có con đường nào được trải nhựa sẵn giữa các thị trấn.

Vua BanQ muốn đi thị sát vương quốc trong vòng ~M~ ngày. Mỗi ngày, ông chọn một thị trấn để đến, tạo thành một chuỗi các thị trấn ~c = [c_1, c_2, ..., c_m]~, trong đó ~c_i~ là thị trấn mà ông đến vào ngày thứ ~i~.

• Ban đầu (trước ngày đầu tiên), ông ở thủ đô, tức thị trấn ~1~.
• Vào ngày thứ ~i~, ông di chuyển từ nơi hiện tại đến ~c_i~. Nếu ông đã ở ~c_i~ rồi, ông sẽ không di chuyển.
• Mỗi lần di chuyển từ ~a~ đến ~b~, vua sẽ cho binh lính trải nhựa đường một chiều từ thị trấn ~a~ đến thị trấn ~b~.
• Hành trình kết thúc tại thị trấn ~c_m~, không cần quay lại thủ đô cũng được.

Sau chuyến đi, các con đường được trải nhựa tạo thành một đồ thị có hướng với các đỉnh là thị trấn, và các cạnh là những con đường một chiều mà vua đã đi qua. Vì lo cho dân nên nhà vua muốn sau khi kết thúc chuyến đi thì người dân có thể đi từ bất kỳ thị trấn nào đến bất kỳ thị trấn khác bằng hệ thống đường đã trải nhựa.

Bạn hãy giúp nhà vua tính xem có bao nhiêu dãy ~c = [c_1, c_2, ..., c_m]~ thỏa mãn điều kiện sau chuyến đi, có thể đi từ mọi thị trấn đến mọi thị trấn khác thông qua những con đường đã trải nhựa nhé.

Input

Một dòng duy nhất chứa hai số nguyên ~N~ và ~M~ (~2 ≤ N ≤ 300, 1 ≤ M ≤ 300~).

Output

In ra một số nguyên là số dãy các thị trấn thỏa mãn điều kiện, modulo ~10^9 + 7~.

Sample Input 1

3 3

Sample Output 1

2

Sample Input 2

150 300

Sample Output 2

734286322

Sample Input 3

300 150

Sample Output 3

0

Giải thích

Trong testcase 1, như hình dưới đây điều kiện chỉ được thỏa mãn khi ~ c = (2,3,1) ~ hoặc ~ c = (3,2,1) ~. Các dãy như ~ c = (2,3,2) ~, ~ c = (2,1,3) ~, ~ c = (1,2,2) ~ không thỏa mãn điều kiện.

Mô tả vấn đề

Có một lưới với ~H~ hàng and ~W~ cột.

Ô ở hàng thứ i và cột thứ j chứa một chuỗi ~S_{i,j}~ có độ dài là ~5~ .

Các hàng được đánh số từ ~1~ đến ~H~ , và các cột được đánh dấu bằng các chứ cái tiếng Anh viết hoa từ A đến ký tự thứ ~W~ trong bảng chữ cái.

Có chính xác một ô trong lưới chứa chuỗi snuke . Tìm chuỗi này trong lưới và thông báo vị trí của nó.

Ví dụ, ô ở hàng thứ 6 và cột thứ 8 là H6 .

Ràng buộc cho vấn đề:

• ~1≦H, W≦26~
• Độ dài của chuỗi ~S_{i,j}~ là ~5~ .
• ~S_{i,j}~ chứa các ký tự tiếng anh viết thường ( a - z ).
• Có chính xác một chuỗi trong lưới là snuke .

Input

Đầu vào được cung cấp theo định dạng sau:

~H~ ~W~

~S_{1,1}~ ~S_{1,2}~ ~...~ ~S_{1,W}~

~S_{2,1}~ ~S_{2,2}~ ~...~ ~S_{2,W}~

~:~

~S_{H,1}~ ~S_{H,2}~ ~...~ ~S_{H,W}~

Output

In ra vị trí của chuỗi snuke trong lưới, không chứa ký tự dấu cách ở giữa.

Sample Input 1

15 10
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snuke snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake

Sample Output 1

H6

Sample Input 2

1 1
snuke

Sample Output 2

A1

Báo cáo vấn đề

Snuke có một lưới với ~ H ~ hàng và ~ W ~ cột. Hình vuông ở hàng ~ i ~ -th và cột ~ j ~ -th chứa ký tự ~ S_ {i, j} ~.

Anh ta có thể thực hiện hai loại hoạt động sau trên lưới:

• Đảo ngược thứ tự của các ô vuông trong một hàng đã chọn.
• Đảo ngược thứ tự của các ô vuông trong một cột đã chọn.

Ví dụ: đảo ngược hàng thứ ~ 2 ~ , sau đó đảo ngược cột thứ ~ 4 ~ sẽ cho kết quả như sau:

Bằng cách thực hiện các thao tác này bất kỳ số lần nào theo thứ tự bất kỳ, có thể thu được bao nhiêu vị trí của ký tự trên lưới?

Hạn chế

• ~ 1 ≦ H, W ≦ 200 ~
• ~ S_ {i, j} ~ là một chữ cái tiếng Anh viết thường (a - z).

Đầu vào

Đầu vào được cung cấp từ Đầu vào chuẩn ở định dạng sau:

~ H ~ ~ W ~

~ S_ {1,1} ~ ~ S_ {1,2} ~ ~ ... ~ ~ S_ {1, W} ~

~ S_ {2,1} ~ ~ S_ {2,2} ~ ~ ... ~ ~ S_ {2, W} ~

~: ~

~ S_ {H, 1} ~ ~ S_ {H, 2} ~ ~ ... ~ ~ S_ {H, W} ~

Đầu ra

In số lượng vị trí ký tự trên lưới có thể nhận được, modulo ~ 1000000007 (= 10 ^ 9 + 7) ~.

Đầu vào Mẫu 1

2 2
cf
cf

Đầu ra Mẫu 1

6

Có thể nhận được ~ 6 ~ vị trí ký tự sau:

Đầu vào Mẫu 2

1 12
codefestival

Đầu ra Mẫu 2

2