Farmer John 的农场是一个 $N \times N$ 的网格（$1 \le N \le 500$），每个格子标有一个字母。例如：

```
ABCD
BXZX
CDXB
WCBA
```

每天，奶牛 Bessie 从左上角的格子走到右下角的格子，每一步只能向右或向下移动一个格子。Bessie 会记录下她走过的路径所生成的字符串，这个字符串由她经过的格子上的字母组成。然而，如果这个字符串是一个回文串（即正读和反读相同），她会感到非常困惑，因为她会分不清自己走过的方向。请帮助 Bessie 计算她可以走的不同路径中，对应回文串的数量。即使生成相同回文串的方式不同，也需要分别计数。请输出答案对 1,000,000,007 取模的结果。

输入的第一行包含 $N$，接下来的 $N$ 行包含网格的 $N$ 行。每行包含 $N$ 个字符，字符范围为 A..Z。

请输出 Bessie 可以走的不同回文路径的数量，对 1,000,000,007 取模。

Bessie 可以生成以下回文串：

- 1 个 "ABCDCBA"
- 1 个 "ABCWCBA"
- 6 个 "ABXZXBA"
- 4 个 "ABXDXBA"