Problem description

Krasnale Algoś i Buguś chcą rozstrzygnąć, który z nich jest lepszym strategiem.

Rozgrywka odbywa się na skierowanym grafie acyklicznym o N wierzchołkach ponumerowanych od 1 do N oraz M krawędziach.

Na początku gry na wierzchołkach 1 i 2 leży po jednym żetonie. Następnie krasnale wykonują ruchy na zmianę, zaczynając od Algosia.

W jednym ruchu gracz wybiera jeden z dwóch żetonów. Jeśli wybrany żeton znajduje się aktualnie na wierzchołku u, gracz musi przesunąć go na dowolny wierzchołek v, dla którego istnieje skierowana krawędź z u do v. Nawet jeśli oba żetony znajdują się na tym samym wierzchołku, w jednym ruchu przesuwany jest dokładnie jeden z nich.

Gracz, który nie może wykonać żadnego ruchu, przegrywa.

Algoś i Buguś wybrali już graf, na którym mogliby rozegrać pojedynek. Zastanawiają się jednak nad wszystkimi możliwymi podzbiorami jego krawędzi. Każdy z 2^M podzbiorów krawędzi wyznacza osobną grę: rozgrywaną na grafie zawierającym wszystkie N wierzchołków oraz tylko krawędzie należące do tego podzbioru. Pusty podzbiór krawędzi również jest brany pod uwagę.

Pomóż krasnalom obliczyć, dla ilu podzbiorów krawędzi Algoś ma strategię wygrywającą. Wynik należy podać modulo 10⁹ + 7.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N i M, oznaczające liczbę wierzchołków oraz liczbę krawędzi grafu.

W kolejnych M wierszach znajdują się opisy krawędzi. Każdy z nich zawiera dwie liczby całkowite A_i i B_i, oznaczające skierowaną krawędź z wierzchołka A_i do wierzchołka B_i.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać liczbę podzbiorów krawędzi, dla których Algoś ma strategię wygrywającą, modulo 10⁹ + 7.

Ograniczenia

2 ≤ N ≤ 15, $1 \le M \le \frac{N(N-1)}{2}$, 1 ≤ A_i < B_i ≤ N,
wszystkie pary (A_i,B_i) są różne.

Przykłady

2 1
1 2

1

Wyjaśnienie

$\\$

3 3
1 2
1 3
2 3

6

Wyjaśnienie

$\\$ $\\$

4 2
1 3
2 4

2

5 10
2 4
3 4
2 5
2 3
1 2
3 5
1 3
1 5
4 5
1 4

816