Soluții trimise

E primăvară și se întorc berzele. În satul nostru, stâlpii de la marginea drumului au vârfurile prea ascuțite și din această cauză berzele nu-și pot face cuib. Așa că e tristețe mare la noi… Dar ne-am adunat cu toții și am hotărât ca pe vârful unor stâlpi să instalăm câte un suport orizontal plan, astfel încât să nu-i fie greu unei berze să-și amenajeze cuibul. Avem n stâlpi la marginea drumului, dispuși liniar și numerotați de la 0 la n–1.

Un număr de m săteni au venit cu câte o restricție de forma i j, însemnând faptul că pe stâlpii din intervalul [i,j] se pot instala cel mult două suporturi pentru cuiburi de berze. Motivele acestor restricții sunt diverse, cum ar fi de pildă apropierea prea mare între anumiți stâlpi. Vom ține seama de ele pentru că vrem ca toți sătenii să fie mulțumiți.

Cunoscând n, m și cele m restricții, să se determine numărul de posibilități ca berzele să-și amenajeze cuiburi pe cei n stâlpi, modulo 700001.