Thành phố nọ tổ chức một cuộc thi chạy kì lạ như sau. Mạng lưới giao thông của thành phố bao gồm ~N~ nút giao thông đánh số từ 0 đến ~(N − 1)~. Có ~M~ con đường nối các nút này. Các con đường này là đường hai chiều. Không có con đường nào nối một nút với chính nó và không có hai con đường nào cùng nối một cặp nút. Đánh số các con đường từ 0 đến ~(M − 1)~. Trên con đường thứ ~i~, ban tổ chức đặt một hộp kẹo có ~3^i~ cái kẹo.

Mỗi thí sinh cần xuất phát từ nút 0, đi qua một số con đường để đến nút ~(N − 1)~. Khi đi qua mỗi con đường, thí sinh cần lấy một chiếc kẹo ra khỏi hộp được đặt sẵn trên con đường đó. Nếu trong hộp không còn kẹo thì thí sinh không được phép đi qua.

Bạn hãy giúp ban tổ chức tính xem có tối đa bao nhiêu thí sinh có thể tham dự cuộc thi.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M (2 ≤ N ≤ 2000, 0 ≤ M ≤ 2000)~.
• ~M~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~u~ và ~v (0 ≤ u, v < N)~ cho biết có một con đường nối hai nút ~u~ và ~v~. Các con đường được đánh số theo thứ tự xuất hiện trong dữ liệu.

Output

• Gọi kết quả bài toán là ~F~. Ghi ra một dòng duy nhất chứa ~F\ mod\ 1000000007~.

Sample

Input #1

3 2
0 1
1 2

Output #1

1

Input #2

4 4
0 1
1 3
0 2
2 3

Output #2

10

Input #3

3 1
0 1

Output #3

0

Input #4

5 0

Output #4

0

Input #5

6 9
1 3
1 2
2 3
0 1
4 5
3 5
0 2
1 4
4 3

Output #5

39

Problem source: Kc97ble - Free Contest 19