Ева и Марија имаат сопствена книжарница. Утрово пристигнале три нови книги, од секоја по најмалку N примероци. Ева ја испразнила најгорната полица и сака на неа да нареди N примероци од книгите, по неколку (0 до N) од секоја од новопристигнатите книги. Но, Марија во последно време развива дизајнерски способности, па на Ева и задава Т правила кои треба да ги исполнуваат така наредените примероци од книги.

На пример, нека имаме пет места на полицата (од лево на десно) и две конкретни ограничувања: “треба да има примероци од точно 1 различна книга од втората до петтата позиција”, и “треба да има примероци од точно 2 различни книги од првата до третата позиција”. За да не ги пишуваме насловите, нека ги означиме трите книги со P, B и C. Во овој случај, постојат дури 6 различни начини на кои може да се наредат пет примероци на петте места на полицата, и тие се:

BPPPP CPPPP PBBBB CBBBB PCCCC BCCCC

Како во примерот даден погоре, нека имаме N места на полицата за N примероци на книги означени со броевите од 1 до N (гледано од лево на десно), и T правила од типот “треба да има примероци од Zi различни книги од Li-тата до Ri-тата позиција”. Нормално, бидејќи Ева и Марија добиле примероци од три нови книги, Zi може да има вредност 1, 2 или 3. На колку различни начини може да биде наредена полицата, така што сите T правила ќе бидат задоволени? Напишете програма која го решава овој проблем.

Влез

Во првиот ред се запишани два цели броја N и T (1 <= N, T <= 300), бројот на примероци и правила, соодветно. Во следните T редови се запишани по три цели броја Zi (1 <= Zi <= 3), Li и Ri (1 <= Li <= Ri <= N), кои ги дефинираат правилата.

Забелешка: Во тест случаи кои носат најмалку 30% од поените, бројот N ќе биде помал или еднаков на 10.

Излез

Во еден ред се печати бројот на начини на кои што може да се подреди полицата. Бидејќи бројот на начини може да биде многу голем, дадете го остатокот при делење на бројот на начини со 1000003.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 512 megabytes

Примери

влез
5 2
1 2 5
2 1 3

излез
6

влез
5 2
1 1 4
3 1 5

излез
0