eolymp
bolt
Try our new interface for solving problems
Məsələlər

Лінія

Лінія

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 122 MiB

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

Завдання

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

Giriş verilənləri

У першому рядку вхідного файла записано натуральне число N (2 ≤ N ≤ 1000) — довжину сторони квадрата з літер. У наступних N рядках записано по N малих літер латинської абетки (не обов’язково різних), що задають розташування літер. Пробілів між літерами немає. Далі записано чарівне слово, що складається з 2N-1 літери (усі — малі літери латинської абетки, не обов’язково різні).

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
3
loc
ogo
gos
logos
Çıxış verilənləri #1
5

Qiymətləndirmə

Набір тестів складається з 3 блоків, для яких додатково виконуються такі умови:

1. 25 % балів: 2 ≤ N ≤ 10.

2. 30 % балів: 10 < N ≤ 100.

3. 45 % балів: 100 < N ≤ 1000.

Пояснення. Є рівно 5 способів викреслити слово logos:

Müəllif Данило Мисак
Mənbə XXVIII Всеукраїнська олімпіада з інформатики 2015 р.