水邊村是一個格局方正的村落，可以被視為 $n\times m$ 的方格。村裡的居民非常迷信，他們給每一個方格一個英文字母代號，表示該地的風水評級。然而村民們發現這樣分類不夠細緻，因此他們對每一塊土地制定兩種新的評級：
1. 從該地開始，重複向上走一格再向左走一格，直到超出領土範圍，並把沿路的評級記錄為代表字串。
2. 從該地開始，重複向左走一格再向上走一格，直到超出領土範圍，並把沿路的評級記錄為代表字串。
例如：假設原始評級為：$\begin{matrix}a & b\\ c & d \end{matrix}$，其右下角的領土兩種新評級分別為 $dba$ 和 $dca$。
如此一共會得到 $2nm$ 個評級，其中評級的字典序愈小其名次愈高，請你計算所有評級的名次。
因為輸出量可能很大，假設座標 $(i, j)$ 的土地用第 $k$ 種方法得到的名次是 $r_{ijk}$，請你回答 $\sum_{i = 0}^ {n-1}\sum_{j = 0}^ {m-1} 2^ i3^ j(r_{ij0}+5r_{ij1})\mod 10^ 9+7$ 即可。
輸入第一行是兩個空白分隔的整數 $n, m$。
接著 $n$ 行每行 $m$ 個小寫英文字母 $c_{i0}c_{i1}\ldots c_{i(m-1)}$，其中 $c_{ij}$ 表示座標 $(i,j)$ 的原始評級。
輸出一行一個整數，表示要求的答案。
在第一筆的範例測試中：
座標 $(0,0)$ 的兩種新評級分別是 a, a，名次分別是 $1, 1$。
座標 $(0,1)$ 的兩種新評級分別是 b, ba，名次分別是 $5, 7$。
座標 $(1,0)$ 的兩種新評級分別是 ba, b，名次分別是 $7, 5$。
座標 $(1,1)$ 的兩種新評級分別是 aba, aba，名次分別是 $3, 3$。
答案為 $2^ 03^ 0(1+5\times 1) + 2^ 03^ 1(5+5\times 7) + 2^ 13^ 0(7+5\times 5) + 2^ 13^ 1(3+5\times 3) = 298$ 再取 $\mod 10^ 9+7$。
IOICamp 2022 Day4 pA
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~23 | 無額外限制 | 100 |