Given a NxN maze, you start at position (1,1) and your exit is at position (N,N), you can only move to the right or down. Each position contains an uppercase character. Every time you move you add that character to form a string. The question is: How many paths lead to the exit form a string that is a palindrome? Input: - First line contains a number N(1 <= N <= 500) - The next N lines, each line contain N uppercase characters. Output: - The answer to the question modulo 1000000007.

Example input:

4
ABCD
BXZX
CDXB
WCBA

Output:

12

Explanation: Possible path

ABCDCBA (1)
ABCWCBA (1)
ABXZXBA (6)
ABXDXBA (4)

The only solution is can think of is brute force (of cource :( ). But the time limit is only 1 sec I don't get any judgement other than TLE. Please help.