小猪佩奇正在散步,走进了森林。多么奇怪的巧合啊!森林呈矩形,由 n 行 m 列组成。我们从上到下用 1 到 n 的数字枚举矩形的行,从左到右用 1 到 m 的数字枚举列。我们将第 r 行和第 c 列交叉处的单元格表示为 (r, c)。
猪最初站在 (1, 1) 号牢房,最后她想站在 (n, m) 号牢房。由于小猪急着回家,她只能从 (r, c) 单元格前往 (r + 1, c) 或 (r, c + 1) 单元格。她不能离开森林。
猪所在的森林非常不寻常。森林中的一些细胞彼此相似,而另一些则看起来非常不同。佩奇喜欢拍照,她每走一步都会拍一张她现在所在牢房的照片。如果在途中拍摄的照片可以以正向和反向顺序查看,并显示相同的照片序列,那么穿过森林的小路就被认为是美丽的。更正式地说,由单元格按访问顺序形成的行应该是回文(您可以在上一个问题中阅读回文的正式定义)。
统计从单元格(1, 1)到单元格(n, m)的美丽路径的数量。由于该数字可能非常大,因此请确定除以 109 + 7 后的余数。
输入
第一行包含两个整数 n, m (1 ≤ n, m ≤ 500) — 字段的高度和宽度。
以下 n 行每行包含 m 个小写英文字母,标识森林的细胞类型。相同的单元格用相同的字母表示,不同的单元格用不同的字母表示。
输出
打印一个整数 — 美丽路径的数量以 109 + 7 为模。
示例
输入 #1
3 4 aaab baaa abba
输出 #1
3
注意
图片说明了样本测试的可能性。