#include <bits/stdc++.h>
using namespace std;
using i128 = __int128_t;
using u128 = __uint128_t;
const long long MOD = 998244353;
const long double PI = 3.141592653589793238;
const long long pi = 31415926;
const long long inf = 1000000000000000000;
const long long small_inf = INT_MAX;
long long int modpow(long long int x, long long int n,
                     long long int mod = MOD) {
  long long int res = 1;
  while (n > 0) {
    if (n & 1) res = res * x % mod;
    x = x * x % MOD;
    n >>= 1;
  }
  return res;
}
long long int power(long long int x, long long int n) {
  long long int res = 1;
  while (n > 0) {
    if (n & 1) res = res * x;
    x = x * x;
    n >>= 1;
  }
  return res;
}
void init() {}
void solve() {
  int n, m;
  cin >> n >> m;
  std::vector<int> v[2][n + 1];
  vector<pair<int, pair<long long int, long long int>>> v1[2 * n + 1];
  for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    v[0][x].push_back(y);
    v[1][y].push_back(x);
    v1[x].push_back(make_pair(y, make_pair(0, 1)));
    v1[n + y].push_back(make_pair(n + x, make_pair(0, 1)));
  }
  for (int i = 1; i <= n; i++) {
    v1[i].push_back(make_pair(n + i, make_pair(1, 0)));
    v1[n + i].push_back(make_pair(i, make_pair(1, 0)));
  }
  std::vector<std::vector<long long>> dist(
      2, std::vector<long long int>(n + 1, inf));
  dist[0][1] = 0;
  for (int fu = 0; fu <= 30; fu++) {
    int f = fu % 2;
    set<pair<long long int, int>> s;
    for (int i = 1; i <= n; i++) {
      if (dist[f][i] != inf) s.insert(make_pair(dist[f][i], i));
    }
    std::vector<int> vis(n + 1, 0);
    while (!s.empty()) {
      pair<long long int, int> p = *s.begin();
      s.erase(s.begin());
      int x = p.second;
      long long int d = p.first;
      if (vis[x]) continue;
      vis[x] = 1;
      for (auto y : v[f][x]) {
        if (!vis[y] && d + 1 < dist[f][y]) {
          dist[f][y] = d + 1;
          s.insert(make_pair(d + 1, y));
        }
      }
    }
    for (int i = 1; i <= n; i++) {
      dist[f ^ 1][i] = min(dist[f ^ 1][i], dist[f][i] + power(2, fu));
    }
  }
  if (dist[0][n] != inf || dist[1][n] != inf) {
    cout << min(dist[0][n], dist[1][n]) % MOD << endl;
    return;
  }
  vector<pair<long long int, long long int>> dis(2 * n + 1,
                                                 make_pair(inf, inf));
  {
    set<pair<pair<long long int, long long int>, int>> s;
    for (int i = 1; i <= n; i++) {
      if (dist[0][i] < inf) dis[i] = make_pair(0, dist[0][i]);
      s.insert(make_pair(dis[i], i));
    }
    std::vector<int> vis(2 * n + 1, 0);
    while (!s.empty()) {
      pair<pair<long long int, long long int>, int> p = *s.begin();
      s.erase(s.begin());
      if (vis[p.second]) continue;
      vis[p.second] = 1;
      int x = p.second;
      long long int num = p.first.first, d = p.first.second;
      for (auto y : v1[x]) {
        if (vis[y.first] || make_pair(num + y.second.first,
                                      d + y.second.second) >= dis[y.first])
          continue;
        dis[y.first] = make_pair(num + y.second.first, d + y.second.second);
        s.insert(make_pair(dis[y.first], y.first));
      }
    }
  }
  pair<long long int, long long int> p;
  if (dis[n].first < dis[2 * n].first)
    p = dis[n];
  else if (dis[2 * n].first < dis[n].first)
    p = dis[2 * n];
  else if (dis[2 * n].second < dis[n].second)
    p = dis[2 * n];
  else
    p = dis[2 * n + 1];
  long long int ans = p.second % MOD;
  for (int i = 30; i <= 30 + p.first - 1; i++) {
    ans += modpow(2, i);
    ans %= MOD;
  }
  cout << ans << endl;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  int t23 = 1, tt23 = 1;
  init();
  while (tt23 <= t23) {
    solve();
    tt23++;
  }
  cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC
       << "ms\n";
}
