sarpe2

Sarpe2

== include(page="template/taskheader" task_id="sarpe2") ==

Poveste şi cerinţă...

HM are o matrice de $NxN$ elemente şi un vector de $M$ elemente distincte. El doreşte să potrivească vectorul peste matrice ca şi cum acesta ar fi un şarpe: alege o pozitie $(x, y)$ pentru începutul vectorului şi apoi potriveşte restul elementelor ducându-se în oricare dintre cele opt elemente adiacente ale poziţiei curente (bineînteles fără a ieşi din matrice).
HM ar dori să ştie în câte moduri poate potrivi vectorul peste matricea dată.

h2. Date de intrare

Fişierul de intrare $sarpe2.in$ ...

Fişierul de intrare $sarpe2.in$ se află doua numere $N$ şi $M$ reprezentând dimensunea matricei, respectiv dimensiunea vectorului de potrivit.
A doua linie din fişier conţine $M$ elemente *distincte* reprezentând elementele vectorului de potrivit.
Următoarele $N$ linii, cu $N$ elemente fiecare, descriu matricea, elementul $j$ de pe linia $i$ reprezentând valoarea de pe linia $i$ şi coloana $j$ a matricei.

h2. Date de ieşire

În fişierul de ieşire $sarpe2.out$ ...

În fişierul de ieşire $sarpe2.out$ trebuie afişat numarul de moduri în care vectorul se poate potrivi peste matrice *modulo 666013*.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 1.000$
* $1 ≤ M ≤ 100.000$
* Vectorul si matricea conţin elemente în intervalul $[0, 100.000]$

h2. Exemplu
table(example). |_. sarpe2.in |_. sarpe2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 3
1 5 4
0 1 5 4
1 5 4 3
4 7 8 2
0 5 4 1
| 6

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="sarpe2") ==

6655