#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
using namespace std;
long long poww(long long a, long long b, long long md) {
  return (!b ? 1
             : (b & 1 ? a * poww(a * a % md, b / 2, md) % md
                      : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 2000 * 100 + 5;
const long long inf = 9223372036854775807;
const long long mod = 998244353;
const int lg = 20;
long long n, m, d[maxn * lg], cnt, ans;
pair<long long, long long> dis[maxn * 2];
set<pair<pair<long long, long long>, int>> s;
vector<int> vr[maxn * 4];
vector<pair<long long, long long>> adj[maxn * lg], g[maxn];
vector<pair<int, pair<long long, long long>>> moj[maxn * 2];
pair<long long, long long> operator+(pair<long long, long long> x,
                                     pair<long long, long long> y) {
  return {x.first + y.first, x.second + y.second};
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n >> m;
  int u, v;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v;
    adj[u].push_back({v, 1});
  }
  for (int i = 1; i <= n; i++) {
    g[i] = adj[i];
  }
  for (int i = 1; i < lg; i++) {
    for (int j = 1; j <= n; j++) {
      for (auto u : g[j]) {
        if (i & 1)
          adj[u.first + i * n].push_back({j + i * n, u.second});
        else
          adj[j + i * n].push_back({u.first + i * n, u.second});
      }
      adj[(i - 1) * n + j].push_back({i * n + j, (1 << (i - 1))});
    }
  }
  vr[0].push_back(1);
  memset(d, 63, sizeof d);
  d[1] = 0;
  for (int i = 0; i < 4 * maxn; i++) {
    for (auto v : vr[i]) {
      if (d[v] < i) continue;
      for (auto u : adj[v]) {
        if (d[u.first] > d[v] + u.second && d[v] + u.second < 4 * maxn) {
          d[u.first] = d[v] + u.second;
          vr[d[v] + u.second].push_back(u.first);
        }
      }
    }
  }
  ans = mod;
  for (int i = 0; i < lg; i++) {
    ans = min(ans, d[i * n + n]);
  }
  if (ans < 4 * maxn) {
    cout << ans << endl;
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    for (auto u : g[i]) {
      moj[i].push_back({u.first, {0, 1}});
    }
    moj[i].push_back({i + n, {1, 0}});
  }
  for (int i = n + 1; i <= 2 * n; i++) {
    for (auto u : g[i - n]) {
      moj[u.first + n].push_back({i, {0, 1}});
    }
    moj[i].push_back({i - n, {1, 0}});
  }
  for (int i = 2; i <= 2 * n; i++) {
    dis[i] = {mod, mod};
  }
  s.insert({{0, 0}, 1});
  while ((long long)(s).size()) {
    auto h = s.begin();
    v = h->second;
    s.erase(h);
    for (auto u : moj[v]) {
      if (dis[u.first] > dis[v] + u.second) {
        s.erase(make_pair(dis[u.first], u.first));
        dis[u.first] = dis[v] + u.second;
        s.insert({dis[u.first], u.first});
      }
    }
  }
  dis[n] = min(dis[n], dis[2 * n]);
  cout << (poww(2ll, dis[n].first, mod) + dis[n].second - 1 + mod) % mod;
}
