#include <bits/stdc++.h>
using namespace std;
long long inf = 1e9;
long long mod = 998244353;
long long n, m, k, res;
vector<vector<long long> > g, w, G, W;
vector<long long> d;
set<pair<int, int> > se;
set<pair<long long, int> > SE;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  k = 19;
  g.resize(k * n);
  w.resize(k * n);
  G.resize(n + n);
  W.resize(n + n);
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    for (int j = 0; j < k; ++j) {
      if (j % 2) {
        g[k * b + j].push_back(k * a + j);
        w[k * b + j].push_back(1);
      } else {
        g[k * a + j].push_back(k * b + j);
        w[k * a + j].push_back(1);
      }
    }
    G[a].push_back(b);
    W[a].push_back(1);
    G[n + b].push_back(n + a);
    W[n + b].push_back(1);
  }
  for (int j = 0; j + 1 < k; ++j) {
    for (int a = 0; a < n; ++a) {
      g[k * a + j].push_back(k * a + j + 1);
      w[k * a + j].push_back(1 << j);
    }
  }
  for (int a = 0; a < n; ++a) {
    G[a].push_back(a + n);
    W[a].push_back(1 << 20);
    G[a + n].push_back(a);
    W[a + n].push_back(1 << 20);
  }
  d.assign(k * n, inf);
  d[0] = 0;
  se.insert({d[0], 0});
  while (!se.empty()) {
    int v = se.begin()->second;
    int D = se.begin()->first;
    se.erase(se.begin());
    for (int i = 0; i < g[v].size(); ++i) {
      int to = g[v][i];
      if (d[to] > d[v] + w[v][i]) {
        se.erase({d[to], to});
        d[to] = d[v] + w[v][i];
        se.insert({d[to], to});
      }
    }
  }
  res = inf;
  for (int j = 0; j < k; ++j) res = min(res, d[k * (n - 1) + j]);
  if (res < inf) {
    cout << res << endl;
    return 0;
  }
  d.assign(n + n, inf * inf);
  d[0] = 0;
  SE.insert({d[0], 0});
  while (!SE.empty()) {
    int v = SE.begin()->second;
    long long D = SE.begin()->first;
    SE.erase(SE.begin());
    for (int i = 0; i < G[v].size(); ++i) {
      int to = G[v][i];
      if (d[to] > d[v] + W[v][i]) {
        SE.erase({d[to], to});
        d[to] = d[v] + W[v][i];
        SE.insert({d[to], to});
      }
    }
  }
  res = min(d[n - 1], d[2 * n - 1]);
  long long a = res >> 20;
  long long b = res - (a << 20) - 1;
  res = 1;
  while (a--) res = 2 * res % mod;
  cout << (res + b) % mod << endl;
  return 0;
}
