Ферма Джона представлена решёткой n * n полей. Каждое поле представлено символом латинского алфавита. Например:

ABCD
BXZX
CDXB
WCBA

Каждый день корова Беси прогуливается из верхнего левого угла в правый нижний, каждый раз двигаясь на один шаг вправо или вниз. Беси записывает в строку буквы, по которым прошлась. Она огорчится, если у неё получится палиндром (слово, которое читается одинаково слева направо и справа налево), поскольку тогда она запутается, в каком направлении двигалась.

Помогите Беси определить количество различных маршрутов которыми она может получить палиндромы. Различные пути, которыми получаются одинаковые палиндромы учитывать множество раз. Выведите свой ответ по модулю 109 + 7.

Входные данные

Первая строка содержит n (1 ≤ n ≤ 500), последующие n строк содержат n строк решётки, описывающей поля. Каждая строка содержит n символов в интервале A..Z.

Выходные данные

Выведите количество различных путей Беси, формирующих палиндромы по модулю 109 + 7.

Пример

Беси может сделать следующие палиндромы:

1 x "ABCDCBA"
1 x "ABCWCBA"
6 x "ABXZXBA"
4 x "ABXDXBA"