eolymp
Задачі

Лінія

Лінія

Орися розставила на аркуші в клітинку n2 літер у формі квадрата n * n і хоче викреслити однією лінією деякі літери у такий спосіб: вона починає викреслювати літери, починаючи з лівої верхньої букви, і веде лінію то праворуч, то вниз; останньою літерою вона викреслює праву нижню. Таким чином, дівчина викреслить рівно 2n - 1 літеру. При цьому Орися хоче, щоб уздовж лінії, яку вона проведе, було записано певне чарівне слово.

Напишіть програму, яка для заданих розташування літер і чарівного слова визначить, у скільки різних способів Орися може його викреслити, та виведе відповідь за модулем простого числа 1 000 003.

Вхідні дані

У першому рядку записано натуральне число n (2n1000) - довжину сторони квадрата з літер. У наступних n рядках записано по n малих літер латинської абетки (не обов'язково різних), що задають розташування літер. Пробілів між літерами немає. Далі записано чарівне слово, що складається з 2n - 1 літери (малі літери латинської абетки, не обов'язково різні).

Вихідні дані

Вивести єдине число - остачу від ділення кількості способів, у які Орися може викреслити чарівне слово, на число 1 000 003.

Приклад

Існує в точності 5 способів викреслити слово logos:

prb7384_

Ліміт часу 1 секунда
Ліміт використання пам'яті 122.17 MiB
Вхідні дані #1
3
loc
ogo
gos
logos
Вихідні дані #1
5
Автор Данило Мисак
Джерело 2015 XXVIII Всеукраїнська олімпіада з інформатики