Орися розставила на аркуші в клітинку N^2 літер у формі квадрата N*N і хоче викреслити однією лінією деякі літери у такий спосіб: вона починає викреслювати літери, починаючи з лівої верхньої букви, і веде лінію то праворуч, то вниз; останньою літерою вона викреслює праву нижню. Таким чином, дівчина викреслить рівно 2N-1 літеру. При цьому Орися хоче, щоб уздовж лінії, яку вона проведе, було записано певне чарівне слово.
Завдання
Напишіть програму, яка для заданих розташування літер і чарівного слова визначить, у скільки різних способів Орися може його викреслити, та виведе відповідь за модулем простого числа 1 000 003.
У першому рядку вхідного файла записано натуральне число N (2 ≤ N ≤ 1000) — довжину сторони квадрата з літер. У наступних N рядках записано по N малих літер латинської абетки (не обов’язково різних), що задають розташування літер. Пробілів між літерами немає. Далі записано чарівне слово, що складається з 2N-1 літери (усі — малі літери латинської абетки, не обов’язково різні).
Вихідний файл повинен містити єдине число — остачу від ділення кількості способів, у які Орися може викреслити чарівне слово, на число 1 000 003.
Набір тестів складається з 3 блоків, для яких додатково виконуються такі умови:
1. 25 % балів: 2 ≤ N ≤ 10.
2. 30 % балів: 10 < N ≤ 100.
3. 45 % балів: 100 < N ≤ 1000.
Пояснення. Є рівно 5 способів викреслити слово logos: