#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define all(x) (x).begin(), (x).end()
#define fsp(x) fixed << setprecision(x)
const ll inf = LLONG_MAX;
const long double pi = acos(-1);
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

//素数判定
//#include <cmath>
bool is_prime(long long n) {
	if (n == 1) return false;
	if (n == 2) return true;
	if (n % 2 == 0) return false;
	for (long long i = 3; i <= sqrt(n); i += 2) {
		if (n % i == 0) return false;
	}
	return true;
}

//二項係数 mod p
//#include <vector>
long long modinv(long long n, long long p) {
	long long a = p, u = 1, v = 0;
	while (a) {
		long long t = n / a;
		n -= t * a;
		std::swap(n, a);
		u -= t * v;
		std::swap(u, v);
	}
	u %= p;
	if (u < 0) u += p;
	return u;
}

std::vector<long long> factorial;
std::vector<long long> factorial_inv;
void make_table(long long n, long long p) {
	factorial.resize(n, 1);
	factorial_inv.resize(n, 1);
	for (long long i = 2; i <= n; i++) {
		factorial[i] = factorial[i - 1] * i % p;
	}
	factorial_inv[n] = modinv(factorial[n], p);
	for (long long i = n - 1; i >= 2; i--) {
		factorial_inv[i] = factorial_inv[i + 1] * (i + 1) % p;
	}
}

long long combination(long long n, long long r, long long p) {
	r = std::min(r, n - r);
	long long ret = factorial[n] * factorial_inv[r] % p;
	ret *= factorial_inv[n - r];
	ret %= p;
	return ret;
}

int main() {
	//ios::sync_with_stdio(false);
	//cin.tie(nullptr);
	const ll p = 1e9 + 7;
	//const ll p = 998244353;

	ll n, m;
	cin >> n >> m;

	map<ll, ll> mp;
	ll x = m;
	for (ll i = 2; i <= x; i++) {
		if (is_prime(x)) {
			mp[x]++;
			break;
		}
		if (!is_prime(i)) continue;
		ll cnt = 0;
		while (x % i == 0) {
			x /= i;
			cnt++;
		}
		mp[i] += cnt;
	}

	make_table(1e7, p);
	ll ans = 1;
	for (auto i = mp.begin(); i != mp.end(); i++) {
		ll a = (i -> first), b = (i -> second);
		ans *= combination(b + n - 1, n - 1, p);
		ans %= p;
	}
	cout << ans << endl;
}

#include<bits/stdc++.h>
using namespace std;

using Weight = long long;
using Vertex = int;
struct Edge {Vertex from, to; Weight weight;};
using Graph = std::vector<std::vector<Edge>>;

std::vector<std::vector<Vertex>> connected_component(const Graph& G) {
  std::vector<std::vector<Vertex>> cc;
  std::vector<bool> used(G.size());
  std::function<void(int)> dfs = [&](int v) {
    cc.back().push_back(v);
    used[v] = true;
    for(const auto& e: G[v]) if(!used[e.to]) dfs(e.to);
  };
  for(Vertex v = 0; v < G.size(); ++v) if(!used[v]) {
    cc.push_back(std::vector<Vertex>());
    dfs(v);
  }
  return cc;
}

using I = long long;

I com2(I n) {return n * (n - 1) / 2;}

bool check(const auto& G, auto s) {
  vector<int> color(G.size(), -1);
  function<bool(Vertex, int)> dfs = [&](auto v, auto c) {
    if(color[v] != -1) return color[v] == c;
    color[v] = c;
    c ^= 1;
    for(const auto& e: G[v]) if(!dfs(e.to, c)) return false;
    return true;
  };
  return dfs(s, 0);
}

int main() {
  I N, M;
  cin >> N >> M;
  Graph G(N);
  for(auto i=0; i<M; ++i) {
    int u, v;
    cin >> u >> v;
    --u; --v;
    G[u].push_back({u, v});
    G[v].push_back({v, u});
  }

  auto cc = connected_component(G);
  auto V = N - count_if(begin(cc), end(cc), [](const auto& v) {return v.size() == 1;});
  auto ans = N * N - V * V;
  I twocol = 0, obscure = 0;
  for(auto c: cc) if(c.size() != 1) {
    if(check(G, *begin(c))) ++twocol;
    else                    ++obscure;
  }
  ans += 2 * twocol + obscure;
  ans += 4 * com2(twocol) + 2 * com2(obscure);
  ans += 2 * twocol * obscure;
  cout << ans << endl;
}
