두 얼간이가 거리를 걷고 있었다...

첫 번째 얼간이: 엄청 좋은 문제를 생각해 냈어. 그러니까 방향 비순환 그래프, 즉 DAG가 있고... 각 간선에 가중치 $0$ 또는 $1$을 부여해서, 어떤 두 정점 사이에서도 경로의 가중치가 선택한 경로에 따라 달라지지 않도록 하는 거야...

두 번째 얼간이: 음... 그런데 어떤 두 정점 사이에 경로가 없으면?

첫 번째 얼간이: 아, 그래, 경로가 여러 개 존재하면 그 경로들의 가중치가 모두 같아야 한다는 거지. 아무튼 그런 가중치 부여 방법의 수를 구하는 거야.

두 번째 얼간이: 응, 좋은 문제네...

다행히 그때 그들은 얼간이가 아닌 친구를 만났다.

얼간이가 아닌 친구: 너희는 분명 그걸 못 풀겠지. 다시 말해, 쩔쩔매고 있는 거야. 하지만 나는 좀 더 간단한 문제를 풀 수 있어. 정점 사이의 거리가 선택한 경로에 따라 달라지지 않도록 하라고 할 수는 없지만, 거리를 $2$로 나눈 나머지가 달라지지 않도록 하라고는 할 수 있지...

첫 번째와 두 번째 얼간이: orz

이제 형식적으로 설명하자. 정점 $N$개와 간선 $M$개로 이루어진 방향 그래프가 주어진다. 정점에는 $1$부터 $N$까지 번호가 붙어 있으며, 모든 방향 간선 $(u,v)$에 대해 $u<v$가 성립한다. 각 간선에 값 $0$ 또는 $1$을 부여하는 것을 간선 색칠이라고 한다. 간선 $(u,v)$의 값을 $w(u,v)$로 나타낸다.

정점 $u$와 $v$ 사이의 경로는 $a_1=u$, $a_k=v$를 만족하는 정점들의 수열 $(a_1,\ldots,a_k)$이다. 또한 $1$부터 $k-1$까지의 모든 $i$에 대해 간선 $(a_i,a_{i+1})$이 존재해야 한다. 경로의 가중치는 그 경로에 있는 모든 간선의 가중치의 합, 즉 $w(a_1,a_2)+\ldots+w(a_{k-1},a_k)$이다.

모든 정점 쌍 $(u,v)$와 그 사이의 모든 경로 쌍에 대해, 두 경로의 가중치를 $2$로 나눈 나머지가 같다면 색칠 $w$를 좋은 색칠이라고 한다.

좋은 색칠의 수는 클 수 있으므로, 그 수를 $10^9+7$로 나눈 나머지를 출력하라.

입력

첫 번째 줄에 자연수 $N$과 $M$이 주어진다.

다음 $M$개의 줄에는 그래프의 간선을 나타내는 서로 다른 수의 쌍 $u$, $v$가 주어진다. 이들은 $1\le u<v\le N$을 만족한다.

출력

한 줄에 좋은 색칠의 수를 $10^9+7$로 나눈 나머지를 출력하라.

서브태스크

모든 서브태스크에서 $1\le N\le400$, $0\le M\le400$이 성립한다.

예제

입력 1

4 4
1 2
2 3
3 4
1 4

출력 1

8

참고

경로 $1\to2\to3\to4$와 $1\to4$의 가중치를 $2$로 나눈 나머지는 같아야 한다. 간선 $(1,4)$에 가중치 $0$을 부여하면, 나머지 간선 중 가중치가 $1$인 간선의 수가 짝수여야 하므로 가능한 경우는 $4$가지이다. 간선 $(1,4)$에 가중치 $1$을 부여하면, 나머지 간선 중 가중치가 $1$인 간선의 수가 홀수여야 하므로 이 경우에도 가능한 경우는 $4$가지이다.

입력 2

4 4
1 3
1 4
2 3
2 4

출력 2

16