TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Description

水邊村是一個格局方正的村落,可以被視為 n×m 的方格。村裡的居民非常迷信,他們給每一個方格一個英文字母代號,表示該地的風水評級。然而村民們發現這樣分類不夠細緻,因此他們對每一塊土地制定兩種新的評級:

1. 從該地開始,重複向上走一格再向左走一格,直到超出領土範圍,並把沿路的評級記錄為代表字串。

2. 從該地開始,重複向左走一格再向上走一格,直到超出領土範圍,並把沿路的評級記錄為代表字串。

例如:假設原始評級為:abcd,其右下角的領土兩種新評級分別為 dbadca

如此一共會得到 2nm 個評級,其中評級的字典序愈小其名次愈高,請你計算所有評級的名次。

因為輸出量可能很大,假設座標 (i,j) 的土地用第 k 種方法得到的名次是 rijk,請你回答 i=0n1j=0m12i3j(rij0+5rij1)mod109+7 即可。

Input Format

輸入第一行是兩個空白分隔的整數 n,m

接著 n 行每行 m 個小寫英文字母 ci0ci1ci(m1),其中 cij 表示座標 (i,j) 的原始評級。

  • 1n,m1000

Output Format

輸出一行一個整數,表示要求的答案。

Sample Input 1

2 2
ab
ba

Sample Output 1

298

Sample Input 2

3 4
pknf
xffj
skxk

Sample Output 2

20035

Hints

在第一筆的範例測試中:

座標 (0,0) 的兩種新評級分別是 a, a,名次分別是 1,1
座標 (0,1) 的兩種新評級分別是 b, ba,名次分別是 5,7
座標 (1,0) 的兩種新評級分別是 ba, b,名次分別是 7,5
座標 (1,1) 的兩種新評級分別是 aba, aba,名次分別是 3,3

答案為 2030(1+5×1)+2031(5+5×7)+2130(7+5×5)+2131(3+5×3)=298 再取 mod109+7

Problem Source

IOICamp 2022 Day4 pA

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~23 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 1048576 65536 1 2
1 10000 1048576 65536 1 2
2 10000 1048576 65536 2
3 10000 1048576 65536 2
4 10000 1048576 65536 2
5 10000 1048576 65536 2
6 10000 1048576 65536 2
7 10000 1048576 65536 2
8 10000 1048576 65536 2
9 10000 1048576 65536 2
10 10000 1048576 65536 2
11 10000 1048576 65536 2
12 10000 1048576 65536 2
13 10000 1048576 65536 2
14 10000 1048576 65536 2
15 10000 1048576 65536 2
16 10000 1048576 65536 2
17 10000 1048576 65536 2
18 10000 1048576 65536 2
19 10000 1048576 65536 2
20 10000 1048576 65536 2
21 10000 1048576 65536 2
22 10000 1048576 65536 2
23 10000 1048576 65536 2