Line
Orysia has arranged n^2 letters on a grid sheet in the shape of an n x n square. She wants to cross out some letters with a single line, starting from the top-left letter and moving either to the right or downward, ending at the bottom-right letter. This means she will cross out exactly 2n - 1 letters. Additionally, Orysia wants the letters along the line to spell a specific magical word.
Your task is to write a program that, given the grid of letters and the magical word, calculates how many different ways Orysia can cross out the magical word. The result should be given modulo the prime number 1,000,003.
Input
The first line contains a natural number n (2 ≤ n ≤ 1000), which is the length of the side of the square grid of letters. The following n lines each contain n lowercase Latin letters (which may repeat), representing the grid. There are no spaces between the letters. After the grid, a magical word is provided, consisting of 2n - 1 lowercase Latin letters (which may also repeat).
Output
Output a single number: the remainder when the number of ways Orysia can cross out the magical word is divided by 1,000,003.
Example
There are exactly 5 ways to cross out the word "logos":
