Turcane

Pe un câmp asemănător cu o tablă de șah cu $M$ linii și $N$ coloane, o țurcană se află în pătrățelul de coordonate $(1, 1)$ aflat în colțul din stânga-sus al tablei și vrea să ajungă în pătrățelul de coordonate $(M, N)$ aflat în colțul din dreapta-jos al tablei. Ea poate efectua sărituri de lungime cel mult $P$ la dreapta, de lungime cel mult $Q$ în jos, de lungime cel mult $R$ pe diagonală spre dreapta-jos, precum și săritura calului, adică două pătrățele la dreapta și unul în jos sau două în jos și unul la dreapta. Orice săritură trebuie să schimbe poziția țurcanei.

Se dă un număr întreg $C$.

• Dacă $C = 1$, să se determine numărul minim de sărituri necesare pentru a ajunge în pătrățelul de coordonate $(M, N)$.
• Dacă $C = 2$, să se determine numărul de moduri în care poate să ajungă în pătrățelul de coordonate $(M, N)$, nu neapărat cu număr minim de sărituri.

Se garantează că pentru datele de intrare există cel puțin un mod de a ajunge în pătrățelul $(M, N)$.

Date de intrare

Pe prima linie a fișierului de intrare se află numărul $C$, pe a doua linie numerele întregi $M$ și $N$, iar pe a treia linie numerele întregi $P$, $Q$ și $R$.

Date de ieșire

În fișierul de ieșire se va afișa, corespunzător valorii lui $C$, numărul cerut. Rezultatul se va afișa modulo $1\ 000\ 000\ 007$.

Restricții și precizări

• $1 \leq M, N \leq 1\ 000$
• $0 \leq P \leq N-1$
• $0 \leq Q \leq M-1$
• $0 \leq R \leq min(M-1, N-1)$
• Dacă $P = 0$ nu poate sări la dreapta, dacă $Q = 0$ nu poate sări în jos, iar dacă $R = 0$ nu poate sări pe diagonală.
• Pentru 26 de puncte, $C = 1$, $M = 1$.
• Pentru 15 puncte, $C = 1$, $M = 2$.
• Pentru 7 puncte, $C = 1$, $M = 3$.
• Pentru 7 puncte, $C = 1$, $1 \leq M, N \leq 200$.
• Pentru 8 puncte, $C = 1$, $1 \leq M, N \leq 1\ 000$.
• Pentru 11 puncte, $C = 2$, $1 \leq M, N \leq 5$.
• Pentru 12 puncte, $C = 2$, $1 \leq M, N \leq 200$.
• Pentru 14 puncte, $C = 2$, $1 \leq M, N \leq 1\ 000$.

Exemple

turcane.in

1
4 3
2 3 1

turcane.out

2

turcane.in

2
2 3
2 1 1

turcane.out

8

Explicații

Notăm cu $O_i$ săritura la dreapta cu $i$ pătrățele, cu $V_i$ săritura în jos cu $i$ pătrățele, cu $D_i$ săritura pe diagonală cu $i$ pătrățele, cu $Cd$ săritura calului spre dreapta-jos și cu $Cj$ săritura calului spre jos-dreapta.

Pentru primul exemplu, numărul minim de sărituri este $2$, și avem șase soluții: $V_3 − O_2$ sau $Cd − V_2$ sau $Cj − D_1$ sau $O_2 − V_3$ sau $V_2 − Cd$ sau $D_1 − Cj$.

Pentru al doilea exemplu, numărul soluțiilor distincte este $8$: $O_1 − O_1 − V_1$ sau $O_1 − V_1 − O_1$ sau $O_1 − D_1$ sau $O_2 − V_1$ sau $D_1 − O_1$ sau $V_1 − O_1 − O_1$ sau $V_1 − O_2$ sau $Cd$.