#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstring>
#include <deque>
#include <forward_list>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<int, ll> PIL;
typedef pair<ll, int> PLI;
typedef pair<ll, ll> PLL;
typedef bitset<16> BS;
struct edge {
    int to, cost, id;
};
const double PI = 3.14159265358979323846;
const double EPS = 1E-09;
const ll MOD = 1E+09 + 7; // =998244353;
const ll INFL = 1E18;
const int INFI = 1E09;
const int MAX_N = 20;

struct unionfind {
    vector<int> par, t_rank, siz;
    vector<bool> cyc;
    unionfind(int n) //n要素で初期化(1-indexed)
        : par(n + 1)
        , t_rank(n + 1)
        , siz(n + 1)
    {
        // n要素で初期化
        // 1-indexedになっているので0-indexedで使いたいときは注意
        for (int i = 1; i <= n; i++) {
            par[i] = i;
            siz[i] = 1;
            t_rank[i] = 0;
        }
    }

    // 木の根を求める
    int find(int x)
    {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }

    // xとyの属する集合を併合
    void unite(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return;

        if (t_rank[x] < t_rank[y]) {
            par[x] = y;
            siz[y] += siz[x];
        } else {
            par[y] = x;
            siz[x] += siz[y];
            if (t_rank[x] == t_rank[y])
                t_rank[x]++;
        }
    }

    // xとyが同じ集合に属するか否か
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }

    // xの属するグループのサイズを求める
    int size(int x)
    {
        return siz[find(x)];
    }
};

ll dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };

int N, M;

vector<int> G[MAX_N + 1];

bool used[MAX_N + 1], check[MAX_N + 1];
int C[MAX_N + 1];

void dfs(int v, vector<int>& vec);
ll paint(int i, int c, vector<int>& vec);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    auto uft = unionfind(N);

    fill(C + 1, C + N + 1, -1);

    for (int i = 1; i <= M; i++) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
        uft.unite(a, b);
    }

    ll ans = 1;
    for (int i = 1; i <= N; i++) {
        if (!used[uft.find(i)]) {
            vector<int> vec = { i };
            dfs(i, vec);
            // for (auto v : vec) {
            //     cout << v << " ";
            // }
            // cout << "\n";
            ans *= 3 * paint(0, 0, vec);
            used[uft.find(i)] = true;
        }
    }

    /*
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << "i = " << i << ", j = " << j << ", dp = " << dp[i][j] << "\n";
        }
    }
    */

    cout << ans << "\n";

    return 0;
}

void dfs(int v, vector<int>& vec)
{
    check[v] = true;
    for (auto to : G[v]) {
        if (!check[to]) {
            vec.push_back(to);
            dfs(to, vec);
        }
    }
}

ll paint(int i, int c, vector<int>& vec)
{
    if (i + 1 == vec.size())
        return 1;

    ll res = 0;
    bool usedc[3];
    fill(usedc, usedc + 3, false);
    int v = vec[i], w = vec[i + 1];
    C[v] = c;
    for (auto to : G[w]) {
        if (C[to] != -1)
            usedc[C[to]] = true;
    }
    for (int _c = 0; _c < 3; _c++) {
        if (!usedc[_c])
            res += paint(i + 1, _c, vec);
    }
    C[v] = -1;
    return res;
}
#include <bits/stdc++.h>
using namespace std;

#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename T> using Graph = vector<vector<T>>;
template<typename T> using Spacial = vector<vector<vector<T>>>;
template<typename T> using greater_priority_queue = priority_queue<T, vector<T>, greater<T>>;
constexpr int MOD = 1e9+7;
constexpr int MOD2 = 998244353;
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
char interval[2] = {' ', '\n'};

template<typename T> struct is_plural : false_type{};
template<typename T1, typename T2> struct is_plural<pair<T1, T2>> : true_type{};
template<typename T> struct is_plural<vector<T>> : true_type{};
template<typename T> struct is_plural<complex<T>> : true_type{};
template<> struct is_plural<string> : true_type{};

template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second; }
template<typename T> istream &operator>>(istream &is, vector<T> &vec) { for(auto itr = vec.begin(); itr != vec.end(); ++itr) is >> *itr; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { if(vec.empty()) return os; bool pl = is_plural<T>(); os << vec.front(); for(auto itr = ++vec.begin(); itr != vec.end(); ++itr) os << interval[pl] << *itr; return os; }
template<typename T> istream &operator>>(istream &is, complex<T> &x) { T a, b; is >> a >> b; x = complex<T>(a, b); return is; }
template<typename T> ostream &operator<<(ostream &os, complex<T> &x) { return os << x.real() << ' ' << x.imag(); }

bool CoutYN(bool a, string y = "Yes", string n = "No") { cout << (a ? y : n) << '\n'; return a; }

template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }


/* -------- <templates end> -------- */


void solve() {
  ll a, b; cin >> a >> b;

  vector<int> prime = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 };
  vector<int> pos(72, -1);
  for(int i=0; i<20; ++i) pos[prime[i]] = i;

  vector<ll> dp(1<<20, 0);
  dp[0] = 1;

  for(ll x=a; x<=b; ++x) {
    bitset<20> bs(0);
    for(int i=0; i<20; ++i) {
      bs.set(i, x % prime[i] == 0);
    }

    for(int i=(1<<20)-1; i>=0; --i) {
      if(!dp[i]) continue;
      bitset<20> now(i);
      auto d = now & bs;
      if(d.none()) {
        d = now | bs;
        dp[d.to_ullong()] += dp[i];
      }
    }
  }

  cout << accumulate(ALL(dp), 0LL) << endl;
}


/* -------- <programs end> -------- */


signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  solve();
  return 0;
}
