Cerința

Se dă un tablou tridimensional, de dimensiune \(n\) x \(n\) x \(n\), fiecare element reprezentând o camera. \(m\) dintre acestea sunt blocate și nu pot fi traversate. Dintr-o cameră având coordonatele \((i,j,k)\) te poți deplasa in camerele de coordonate \((i+1,j,k)\), \((i,j+1,k)\) și \((i,j,k+1)\).

Știind că pornești din camera cu coordonate \((1,1,1)\), se cere să se afișeze numărul de moduri modulo \(1234567\) de a ajunge in camera de coordonate \((n,n,n,)\).

Date de intrare

Fișierul de intrare cub_dinamic.in conține pe prima linie numerele n și m, iar pe următoarele m linii câte 3 numere reprezentând coordonatele camerelor blocate.

Date de ieșire

Fișierul de ieșire cub_dinamic.out va conține pe prima linie numărul S, reprezentând numărul de moduri modulo \(1234567\) de a ajunge din camera \((1,1,1)\) în camera \((n,n,n)\).

Restricții și precizări

• 1 ≤ n ≤ 200
• 1 ≤ coordonatele camerelor ≤ n
• 0 ≤ m ≤ n*n*n
• Dacă nu se poate ajunge in camera \((n,n,n)\) sau una dintre camerele \((1,1,1)\) sau \((n,n,n)\) este blocată, atunci se va afișa 0.

Exemplu:

cub_dinamic.in

3 1
2 2 2

cub_dinamic.out

54

Explicație

Există 54 de moduri de a ajunge din camera \((1,1,1)\) în camera \((n,n,n)\) fără a trece prin camere blocate.