Simulare Lot 2018 Baraj 4 Juniori | berze

This was the problem page during the contest. Access the current page here.
Time limit: 0.05s Memory limit: 64MB Input: berze.in Output: berze.out

E primavară ş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 \dots 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 nn stâlpi la marginea drumului, dispuşi liniar şi numerotaţi de la 00 la n1n - 1.

Un număr de mm săteni au venit cu câte o restricţie de forma i ji \ j, însemnând faptul că pe stalpii din intervalul [i,j][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.

Cerinţă

Cunoscând nn, mm şi cele mm restricţii să se determine numărul de posibilităţi ca berzele să-şi amenajeze cuiburi pe cei nn stâlpi, modulo 700 001700 \ 001.

Date de intrare

Fişierul de intrare berze.in conține pe prima linie numerele nn şi mm având semnificaţia din enunţ. Pe următoarele mm linii se găsesc câte două numere naturale ii, jj, reprezentând faptul că în intervalul de stâlpi [i,i+1,i+2,,j][i, i+1, i+2, \dots, j] se pot amenaja cel mult două suporturi pentru cuiburi de berze.

Date de ieșire

Fişierul de ieșire berze.out va conţine pe o singură linie un număr natural ce reprezintă numărul de posibilităţi de a plasa suporturi pentru cuiburi de berze pe cei nn stâlpi.

Restricții și precizări

  • 2m,n1 0002 \leq m, n \leq 1 \ 000
  • 0i<jn10 \leq i < j \leq n - 1
  • cele mm intervale de forma i ji \ j nu sunt neapărat disjuncte
  • pe un stâlp se poate instala cel mult un suport pentru cuib de barză
  • pentru 50%50\% din teste N100N \leq 100

Exemplu

berze.in

4 1
0 2

berze.out

14

Explicație

Notăm cu I un stâlp fără suport pentru cuib de barză şi cu T un stâlp cu suport. Atunci cele 1414 soluţii sunt:

I I I I 
I I I T
T I I I 
T I I T
I T I I 
I T I T
I I T I 
I I T T
T T I I 
T T I T
T I T I 
T I T T
I T T I 
I T T T

Log in or sign up to be able to send submissions!