!problema/fft2d?pic_fft2d.png!

Intrigat de modificările făcute, Nusdeaici s-a decis să calculeze numărul de perechi *(a, b)* cu proprietatea că există măcar un drum orientat de la nodul *(0, a)* la nodul *(F - 1, b)* care nu trece prin niciun nod negru.
 

h2. Date de intrare

Fişierul de intrare $fft2d.in$ ...

Fişierul de intrare $fft2d.in$ va conţine pe prima linie două numere naturale *F* şi *T*. Următoarele *T* linii vor conţine câte o pereche *(h, x)*, reprezentând faptul că nodul de pe nivelul *h* cu indicele *x* este colorat cu negru.

h2. Date de ieşire

În fişierul de ieşire $fft2d.out$ ...

Fişierul de ieşire $fft2d.out$ va conţine un singur număr natural reprezentând numărul
de perechi *(a, b)* cu proprietatea că există măcar un drum orientat de la nodul *(0, a)* la
nodul *(F - 1, b)* care nu trece prin niciun nod negru.

h2. Restricţii

* $... ≤ ... ≤ ...$

● *1 ≤ F ≤ 30*
● *1 ≤ T ≤ 100 000*
● ATENŢIE! Muchiile sunt orientate (deşi în figură nu sunt reprezentate
astfel).*
● “Apam, cum să numim personajul principal?” Răspuns: “Nustiuboss”.
● Pentru teste în valoare de 10 puncte, N ≤ 10
● Pentru alte teste în valoare de 10 puncte, N ≤ 16
● Pentru alte teste în valoare de 30 puncte, K ≤ 2000

h2. Exemplu

table(example). |_. fft2d.in |_. fft2d.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

table(example). |_. fft2d.in |_. fft2d.out |_. explicatii |
| 3 3
0 2
1 1
2 3
| 5
| Există 5 perechi (a, b) cu proprietatea din enunţ. Mai
exact, acestea sunt: (0, 0), (0, 1), (0, 2), (1, 2), (3, 2).
|
| 4 3
0 1
1 1
2 4
| 44
| Există 44 de perechi (a, b) cu proprietatea din enunţ.
Figura de pe prima pagină corespunde acestui exemplu.
|
| 15 10
3 12914
8 10479
12 1039
8 13597
11 2633
12 10668
12 6769
11 4443
7 15697
12 13418
| 268271648
| Va trebui să ne credeţi pe cuvânt.
|

h3. Explicaţie