Лінія
Орися розставила на аркуші в клітинку n^2 літер у формі квадрата n * n і хоче викреслити однією лінією деякі літери у такий спосіб: вона починає викреслювати літери, починаючи з лівої верхньої букви, і веде лінію то праворуч, то вниз; останньою літерою вона викреслює праву нижню. Таким чином, дівчина викреслить рівно 2n - 1 літеру. При цьому Орися хоче, щоб уздовж лінії, яку вона проведе, було записано певне чарівне слово.
Напишіть програму, яка для заданих розташування літер і чарівного слова визначить, у скільки різних способів Орися може його викреслити, та виведе відповідь за модулем простого числа 1 000 003.
Вхідні дані
У першому рядку записано натуральне число n (2 ≤ n ≤ 1000) - довжину сторони квадрата з літер. У наступних n рядках записано по n малих літер латинської абетки (не обов'язково різних), що задають розташування літер. Пробілів між літерами немає. Далі записано чарівне слово, що складається з 2n - 1 літери (малі літери латинської абетки, не обов'язково різні).
Вихідні дані
Вивести єдине число - остачу від ділення кількості способів, у які Орися може викреслити чарівне слово, на число 1 000 003.
Приклад
Існує в точності 5 способів викреслити слово logos:
