loop

Participi la un concurs de robotică unde scopul este să programezi un robețel care se deplasează într-un labirint de dimensiuni $N \times M$. Labirintul este reprezentat printr-o matrice binară, unde $a_{i,j} = 1$ semnifică o celulă blocată, iar $a_{i,j} = 0$ semnifică o celulă liberă. Liniile și coloanele matricei sunt indexate de la $1$.

Înaintea începerii competiției, concurenții primesc matricea binară care descrie labirintul și două celule distincte $(\ell_1, c_1)$ și $(\ell_2, c_2)$ din aceasta. Robețelul tău va fi plasat inițial în celula $(\ell_1, c_1)$ și trebuie să se deplaseze până la celula $(\ell_2, c_2)$, fără să treacă prin celule blocate sau să părăsească labirintul.

Tu trebuie să programezi robețelul, alegând un număr de instrucțiuni $k$ și o secvență de $k$ comenzi de tipurile sus, jos, stânga și dreapta. Fiecare comandă mișcă robețelul cu o unitate în direcția indicată de comandă. După ce ai ales secvența, vei alege și un număr $p$ și vei plasa secvența de comenzi într-o structură repetitivă care se execută de $p$ ori, ca mai jos:

Notăm cu $S_p$ mulțimea de secvențe de comenzi $s$ care, executate secvențial de $p$ ori consecutiv, ar duce robețelul din $(\ell_1, c_1)$ în $(\ell_2, c_2)$ fără să treacă prin celule blocate sau să iasă din matrice. Notăm cu $T_p$ submulțimea de secvențe din $S_p$ al căror număr de comenzi este minim în $S_p$. Mai riguros:

Observăm că $T_p$ va fi vidă dacă $S_p$ este vidă.

Cerință

Se cere să se determine câte elemente are mulțimea $T_k$ pentru toate mulțimile $T_k$ nevide, unde $1 \leq k \leq N \cdot M$, modulo $10^9 + 7$.

Date de intrare

Prima linie va conține $N$ și $M$, dimensiunile matricei, separate printr-un spațiu. A doua linie va conține coordonatele celulei de start, $\ell_1$ și $c_1$, separate printr-un spațiu. A treia linie va conține coordonatele celulei de final, $\ell_2$ și $c_2$, separate printr-un spațiu. Pe următoarele $N$ linii se vor găsi câte $M$ caractere de $0$ sau $1$, reprezentând conținutul celulelor matricei.

Date de ieșire

Pe prima linie se va afișa un număr natural $C$, reprezentând numărul de mulțimi $T_k$ care sunt nevide, unde $1 \leq k \leq N \cdot M$. Pe următoarele $C$ rânduri, se va afișa pe fiecare rând, separat printr-un spațiu, o pereche $(p, r)$, cu semnificația că $r$ este restul numărului de elemente a mulțimii $T_p$ la împărțirea cu $10^9 + 7$.

Afișarea va fi făcută în ordine crescătoare după p.

Restricții și precizări

• $1 \leq N \cdot M \leq 1 \ 700 \ 000$;
• $1 \leq \ell_1, \ell_2 \leq N$ și $1 \leq c_1, c_2 \leq M$;
• $(\ell_1, c_1) \neq (\ell_2, c_2)$.

Exemplul 1

loop.in

5 9
2 1 4 9
010000000
001001000
001000000
000000100
000000000

loop.out

2
1 50
2 6

Explicație

Pentru primul exemplu există două drumuri periodice. Primul tip de drum periodic este acela în care se repetă o singură dată secvența de miscări (are perioada $1$) și există $50$ de astfel de drumuri. Al doilea tip de drum periodic este acela care se repetă de două ori (are perioada $2$) și există $6$ astfel de drumuri distincte (un exemplu ar fi: dreapta, jos, jos, dreapta, dreapta, sus, dreapta corespunzător desenului de mai sus).

Exemplul 2

loop.in

7 10
1 1 7 10
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000

loop.out

2
1 5005
3 10