Орися розставила на аркуші в клітинку \textit{\textbf{N^2}} літер у формі квадрата\textit{\textbf{ N*N }} і хоче викреслити однією лінією деякі літери у такий спосіб: вона починає викреслювати літери, починаючи з лівої верхньої букви, і веде лінію то праворуч, то вниз; останньою літерою вона викреслює праву нижню. Таким чином, дівчина викреслить рівно \textit{\textbf{2N-1}} літеру. При цьому Орися хоче, щоб уздовж лінії, яку вона проведе, було записано певне чарівне слово. \textbf{Завдання} Напишіть програму, яка для заданих розташування літер і чарівного слова визначить, у скільки різних способів Орися може його викреслити, та виведе відповідь за модулем простого числа\textit{\textbf{ 1 000 003}}. \InputFile У першому рядку вхідного файла записано натуральне число N (2 ≤ N ≤ 1000) --- довжину сторони квадрата з літер. У наступних N рядках записано по N малих літер латинської абетки (не обов’язково різних), що задають розташування літер. Пробілів між літерами немає. Далі записано чарівне слово, що складається з 2N-1 літери (усі --- малі літери латинської абетки, не обов’язково різні). \OutputFile Вихідний файл повинен містити єдине число --- остачу від ділення кількості способів, у які Орися може викреслити чарівне слово, на число 1 000 003. \Scoring Набір тестів складається з 3 блоків, для яких додатково виконуються такі умови: 1. 25 \% балів: 2 ≤ N ≤ 10. 2. 30 \% балів: 10 < N ≤ 100. 3. 45 \% балів: 100 < N ≤ 1000. \textbf{Пояснення. }Є рівно 5 способів викреслити слово logos: \includegraphics{https://static.e-olymp.com/content/cb/cbc7d58f7a8bff682483bdc3fc09050819e5e30e.png}