În cel mai recent experiment al lor, renumiţii cercetători Pala şi Lila au plasat un roboţel într-un caroiaj cu N linii şi M coloane numerotate de la 1 la N, respectiv de la 1 la M. La fiecare secundă roboţelul se mişcă pe orizontală sau pe verticală într-una dintre celulele adiacente celulei în care se află, fără a părăsi caroiajul.
Celulele adiacente celulei (x,y) sunt (x,y-1), (x,y+1), (x-1,y), (x+1,y).
În caroiaj există K poziţii inaccesibile în care roboţelul nu poate ajunge niciodată. Scopul experimentului este de a verifica pentru P situaţii în câte moduri poate ajunge roboţelul de la poziţia (x1,y1) la poziţia (x2,y2) în exact T secunde.
Cerinţă
Răspundeţi la P întrebări de forma: În câte moduri poate ajunge roboţelul de la poziţia (x1,y1) la poziţia (x2,y2) în exact T secunde. Deoarece acest număr poate fi destul de mare, va trebui să afişaţi rezultatul modulo 666013.
Date de intrare
Fişierul de intrare robotel.in conţine pe prima linie numerele naturale N M K, separate prin spaţii. Următoarele K linii vor conţine câte o pereche de numere x y care descriu coordonatele unei poziţii inaccesibile. Pe linia următoare se va afla numărul de întrebări P, iar următoarele P linii vor conţine câte cinci numere naturale x1 y1 x2 y2 T, care descriu cate o întrebare astfel: (x1,y1) reprezintă poziţia din care porneşte roboţelul, (x2,y2) poziţia de sosire, iar T timpul în care se mişcă roboţelul, exprimat în secunde.
Date de ieşire
Fişierul de ieşire robotel.out va conţine P linii, pe linia i aflându-se răspunsul la cea de-a i-a întrebare din fişierul de intrare.
Restricţii
• 1 <= N, M <= 15
• 0 <= K <= N*M <= 100
• 1 <= P <= 256
• 1 <= T <= 1 000 000
• Dacă celula din care porneşte roboţelul sau celula în care trebuie să ajungă sunt inaccesibile pentru întrebarea respectivă răspunsul este 0.
• Dacă nu se poate ajunge din celula de pornire în cea de final în T secunde răspunsul este 0.
• Roboţelul nu va staţiona în nicio celulă mai mult de o secundă.