Fie N și K două numere naturale. Toate punctele din plan de coordonate întregi (x,y) cu proprietatea 0 ≤ x ≤ N, 0 ≤ y ≤ N se unesc prin linii orizontale și verticale de lungime 1. Apoi K linii de lungime 1 dintre cele de mai sus se șterg. Definim o cale ca fiind o succesiune continuă de linii orizontale sau verticale de lungime 1, între originea sistemului de axe și punctul de coordonate (N, N), cu lungimea totală 2∙N.

Cerința

Să se determine numărul total de căi distincte. De exemplu, dacă N = 3 și dintre toate liniile desenate se șterg K = 4 linii (liniile subțiri), atunci conform figurilor de mai jos, numărul total de căi distincte va fi 6.

Date de intrare

Fișierul de intrare npath.in conține pe prima linie numerele N și K, despărțite printr-un spațiu, cu semnificaţia de mai sus, iar pe fiecare din următoarele K linii va fi câte un triplet de numere x, y, d având următoarea semnificație:

• x, y reprezintă coordonatele punctului de unde începe să se șteargă o linie.
• d = 1 dacă linia va fi ștearsă pe orizontală către dreapta.
• d = 2 dacă linia va fi ștearsă pe verticală în sus.

Date de ieșire

Fișierul de ieșire npath.out va conține pe prima linie restul împărțirii numărului total de căi distincte la 3000017.

Restricții și precizări

• 1 ≤ N ≤ 5000
• 0 ≤ K ≤ 100
• două căi sunt distincte dacă succesiunea de linii orizontale și verticale diferă prin cel puțin o poziție
• pentru teste în valoare de 52 puncte 0 ≤ K ≤ 15

Exemplu:

npath.in

3 4
1 0 2
2 1 2
2 2 1
1 2 2

npath.out

6

Explicație

N = 3 și K = 4. Din grila inițială se șterg 4 linii și anume:

• Linia verticală dintre punctele de coordonate (1,0) și (1,1)
• Linia verticală dintre punctele de coordonate (2,1) și (2,2)
• Linia orizontală dintre punctele de coordonate (2,2) și (3,2)
• Linia verticală dintre punctele de coordonate (1,2) și (1,3)

-În total sunt 6 moduri diferite de a ajunge din origine în punctul de coordonate (3,3) fără a trece prin liniile șterse (conform figurilor de mai sus). Restul împărțirii lui 6 la 3000017 este 6.