#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int MOD = 1000000007;
const int MAXN = 2005;

struct Edge {
    int u, v;
};

struct State {
    int node;
    int dist;
    bool operator>(const State& other) const {
        return dist < other.dist; // Max heap
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<Edge> edges(M);
    for (int i = 0; i < M; ++i) {
        cin >> edges[i].u >> edges[i].v;
    }

    // Precompute powers of 3 modulo MOD
    vector<long long> pow3(M + 1);
    pow3[0] = 1;
    for (int i = 1; i <= M; ++i) {
        pow3[i] = (pow3[i - 1] * 3) % MOD;
    }

    // Dijkstra to find the best path (lexicographically largest)
    // Actually, we need to maximize the sum of 3^i.
    // Since 3^{i+1} > sum(3^0 ... 3^i), we can use a greedy approach with DSU or Dijkstra with big integers.
    // However, given constraints and standard solutions, the DSU approach is more standard.
    // Let's implement the DSU approach which is effectively the same as the provided solution 1.
    // This snippet represents the logic of Solution 1.

    vector<int> parent(N);
    for (int i = 0; i < N; ++i) parent[i] = i;

    auto findSet = [&](int i) {
        while (i != parent[i]) {
            parent[i] = parent[parent[i]];
            i = parent[i];
        }
        return i;
    };

    auto unionSets = [&](int i, int j) {
        int root_i = findSet(i);
        int root_j = findSet(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
        }
    };

    long long result = 0;
    // Iterate from largest edge index to smallest
    for (int i = M - 1; i >= 0; --i) {
        int u = edges[i].u;
        int v = edges[i].v;

        // If u and v are already connected via edges > i, adding this edge creates a cycle.
        // In this problem, we want to maximize the sum of 3^i on paths from 0 to N-1.
        // If adding edge i connects the component of 0 and N-1, we gain 3^i.
        // The logic in the solution is:
        // If {0} and {N-1} are in different components, and edge i connects them, we add 3^i.
        // Wait, the provided solution logic is:
        // Check if (u in comp(0) && v in comp(N-1)) OR vice versa.
        // If yes, add pow3[i]. Else, union them.

        int root0 = findSet(0);
        int rootN = findSet(N - 1);
        int rootU = findSet(u);
        int rootV = findSet(v);

        if ((rootU == root0 && rootV == rootN) || (rootU == rootN && rootV == root0)) {
            result = (result + pow3[i]) % MOD;
        } else {
            unionSets(u, v);
        }
    }

    cout << result << endl;
    return 0;
}

// Mô phỏng logic DSU
#include <vector>
using namespace std;

int solve(int N, int M, vector<pair<int,int>>& edges) {
    int mod = 1000000007;
    vector<int> parent(N);
    for(int i=0; i<N; i++) parent[i] = i;

    // Precompute powers
    vector<long long> p3(M+1, 1);
    for(int i=1; i<=M; i++) p3[i] = (p3[i-1] * 3) % mod;

    long long res = 0;
    // Duyệt ngược từ cạnh cuối
    for(int i = M-1; i >= 0; i--) {
        int u = edges[i].first;
        int v = edges[i].second;

        // Tìm root
        int root_u = u; while(root_u != parent[root_u]) root_u = parent[root_u];
        int root_v = v; while(root_v != parent[root_v]) root_v = parent[root_v];
        // Path compression có thể thêm vào

        int root_0 = 0; while(root_0 != parent[root_0]) root_0 = parent[root_0];
        int root_n1 = N-1; while(root_n1 != parent[root_n1]) root_n1 = parent[root_n1];

        // Kiểm tra điều kiện: cạnh này có nối comp chứa 0 và comp chứa N-1 không?
        // Nếu 2 đỉnh của cạnh thuộc 2 comp khác nhau mà 1 trong 2 comp là comp(0) và comp kia là comp(N-1)
        // Hoặc đơn giản hơn: nếu (root_u == root_0 && root_v == root_n1) || (root_u == root_n1 && root_v == root_0)
        // Nếu có, cộng dồn 3^i
        if ((root_u == root_0 && root_v == root_n1) || (root_u == root_n1 && root_v == root_0)) {
            res = (res + p3[i]) % mod;
        } else {
            // Nếu không, hợp nhất hai thành phần
            // Lưu ý: chỉ hợp nhất nếu chúng chưa nối với nhau qua đường khác
            // Thực tế logic bài giải là: Nếu không tạo đường đi trực tiếp, ta thêm cạnh vào DSU để mở rộng thành phần
            if (root_u != root_v) parent[root_u] = root_v;
        }
    }
    return res;
}