Prologin, le concours national d'informatique

Énoncé¶

Joseph Marchand se lance un défi, il doit produire une crêpe tout en se promenant sur la plage, promenade qui doit satisfaire certaines contraintes qu'il a définies à l'avance.

Il a commencé par dessiner des disques à certains endroits sur le sol qu'il numérote de 0 à $N$ - 1, le disque 0 correspondant à l'emplacement de son stand à crêpes. Sur chacun d'entre eux, il plante une pancarte indiquant 2 directions pointant chacune vers respectivement 2 autres emplacements.

Sa promenade doit commencer à l'instant 0 au niveau de son stand et à chaque disque rencontré il doit prendre une des deux directions indiquées selon le critère suivant :

la première si le nombre de 1 dans l'écriture binaire du nombre de disques déjà rencontrés est pair
la seconde sinon

Joseph tient à ce que sa crêpe soit parfaite, pour cela il faut impérativement qu'elle soit retournée pile au milieu du temps de cuisson. Pour pouvoir réaliser une telle crêpe il faut donc qu'il se trouve au niveau de son stand aux instants $T$, $T+t$ puis $T+2t$ où $T$ est l'instant de début de cuisson, et $t$ la durée de mi-cuisson, cela sachant qu'il met exactement une seconde (il est très rapide) pour se déplacer d'un disque à l'autre.

À l'instant 0 il met en marche sa poêle, et il ne peut pas lancer directement la cuisson d'une crêpe, il lui faudra attendre au moins son prochain retour sur son stand. Par ailleurs, comme il n'est pas infatigable, Joseph arrêtera sa promenade après la seconde $L$ (il peut encore arrêter la cuisson d'une crêpe à cet instant).

Combien Joseph a-t-il de manières différentes de réaliser une crêpe parfaite ?

Entrée¶

La première ligne contiendra 2 entiers $L$ et $N$, la durée de sa promenade et le nombre de disques qu'il a tracés sur le sol. $N$ lignes suivront, la $i$-ème d'entre elles contiendra 2 entiers qui correspondront dans l'ordre aux 2 directions sur le $i$-ème disque.

Sortie¶

Vous afficherez un seul entier : le nombre de manières différentes pour Joseph de réaliser une crêpe parfaite pendant sa promenade.

Contraintes¶

$1 \le N \le 2\ 500$
$1 \le L \le 2\ 000\ 000$

Attention ! Il n'y a pas de tests de performance pour ce problème, c'est à dire que pour valider les tests de correction il faut déjà avoir la bonne complexité (ie une solution correcte mais trop lente sera jugée non valide).

Contraintes d'exécution

Utilisation mémoire maximum: 64000 kilo-octets
Temps d'exécution maximum: 1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée

Exemple de sortie

Commentaire

Joseph commence à compter :

0 a un nombre pair (0) de bits à 1, il va donc au disque 1
1 a un nombre impair (1) de bits à 1, il va donc au disque 2
2 a un nombre impair (1) de bits à 1, il va donc au disque 0 (son stand à crêpe)
3 a un nombre pair (2) de bits à 1, il va donc au disque 1
4 a un nombre impair (1) de bits à 1, il va donc au disque 2
5 a un nombre pair (2) de bits à 1, il va donc au disque 0 (son stand à crêpe)
6 a un nombre pair (2) de bits à 1, il va donc au disque 1
7 a un nombre impair (3) de bits à 1, il va donc au disque 2
8 a un nombre impair (1) de bits à 1, il va donc au disque 0 (son stand à crêpe)

Joseph peut donc commencer à faire cuire une crêpe après 3 secondes, il retombera sur son stand à crêpe 3 secondes plus tard pour la retourner et enfin, 3 secondes après pour la manger.