Cho lưới ô vuông kích thước ~n~ x ~n~, các hàng đánh số ~1…n~ từ trên xuống dưới, các cột đánh số ~1…n~ từ trái sang phải. Mỗi ô trong lưới chứa một kí tự chữ cái latin in hoa. Xét các đường đi từ ô ~(1;1)~ đến ô ~(n;n)~ chỉ đi từ một ô sang ô kề cạnh bên phải hoặc bên dưới. Mỗi đường đi được đại diện bởi một xâu kí tự là dãy các kí tự trong các ô trên đường đi dọc theo hành trình. Đếm số đường đi có xâu đại diện là xâu đối xứng.

Input

• Dòng 1: số nguyên ~n~ ~(1 \leq n \leq 500)~.
• Dòng 2…~n+1~: dòng ~i+1~ chứa một xâu độ dài ~n~ mô tả hàng ~i~ của lưới.

Output

• Dòng 1: số nguyên là số lượng đường đi có xâu đại diện là xâu đối xứng, lấy phần dư khi chia cho ~(10^9+7)~.

Subtask

• Có ~30\%~ số test có ~n \le 100~
• ~70\%~ còn lại không giới hạn gì thêm

Sample Input 1

4
ABCD
BXZX
CDXB
WCBA

Sample Output 1

12

Explanation:

• Xâu ABCDCBA là đại diện của 1 đường
• Xâu ABCWCBA là đại diện của 1 đường
• Xâu ABXZXBA là đại diện của 6 đường
• Xâu ABXDXBA là đại diện của 4 đường

Một xí nghiệp có một robot dùng để xếp các sản phẩm vào các thùng. Mọi thùng đều có dung tích như nhau. Có đúng hai thùng đang mở sẵn để robot xếp các sản phẩm vào. Mỗi thùng bất kỳ đều chứa được số sản phẩm mà tổng dung tích của chúng không vượt quá dung tích của thùng. Robot có thể thực hiện các thao tác sau:

• Đưa một sản phẩm hiện tại trên dãy băng vào thùng ~1~,
• Đưa một sản phẩm hiện tại trên dãy băng vào thùng ~2~,
• Đóng thùng ~1~ và mở một thùng mới thay thế cho thùng ~1~,
• Đóng thùng ~2~ và mở một thùng mới thay thế cho thùng ~2~.

Các thao tác 1, 2 chỉ có thể thực hiện nếu tổng dung tích của sản phẩm cho vào và các sản phẩm đã có trong thùng không vượt quá dung tích của thùng.

Yêu cầu: Cho biết dung tích mỗi thùng là ~𝑊~, dung tích của ~𝑛 sản~ phẩm trên dãy băng theo thứ tự xuất hiện là ~𝑎_1, 𝑎_2, . . . , 𝑎_𝑛~ , hãy tìm số thùng ít nhất để có thể cho ~𝑛~ sản phẩm vào thùng.

Input

• Dòng thứ nhất là hai số nguyên ~𝑊~ và ~𝑛~;
• Dòng tiếp theo chứa các số mô tả các số ~𝑎_1, 𝑎_2, … , 𝑎_𝑛~.

Output

• Gồm một số duy nhất là số thùng ít nhất cần dùng.

Input

8 6
4 2 5 3 5 4

Output

3

Giải thích

• Đưa ~1~ vào thùng ~1~
• Đưa ~2~ ~3~ ~4~ ~5~ vào thùng ~2~ (cần mở thêm một thùng)
• Đưa ~6~ vào thùng ~1~ (vẫn còn đủ chỗ, không cần mở thêm)

Ràng buộc

• Subtask 1 [10 tests] ~𝑊 ≤ 10^9 ; 𝑛 ≤ 20~
• Subtask 2 [10 tests] ~1 ≤ 𝑎_𝑖 ≤ 2; 𝑊 = 100; 𝑛 ≤ 10^6~
• Subtask 3 [10 tests] ~𝑊 ≤ 30; 𝑛 ≤ 10000~
• Subtask 4 [10 tests] ~𝑊 ≤ 5000; 𝑛 ≤ 100~
• Subtask 5 [10 tests] ~𝑊 ≤ 5000 ; 𝑛 ≤ 10000~