#include <bits/stdc++.h>
using namespace std;
long long modpow(long long a, long long b, long long mod) {
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return res;
}
const long long mod = 998244353;
int log2(int k) {
  int ans = 1;
  while (k > 1) {
    k /= 2;
    ans++;
  }
  return ans;
}
const int MXLG = 19, MXN = 2e5, INF = 1e9;
vector<vector<int> > adj[MXN + 1][MXLG + 2], adj2[MXN + 2][2];
int dist[MXN + 1][MXLG + 2];
pair<int, int> dist2[MXN + 1][2];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  int lg = log2(n);
  for (int i = 0; i < (int)n; i++) {
    dist2[i][0] = dist2[i][1] = {INF, INF};
    adj2[i][0].push_back({i, 1, 1, 0});
    adj2[i][1].push_back({i, 0, 1, 0});
    for (int j = 0; j < (int)lg + 1; j++) {
      if (j < lg) {
        adj[i][j].push_back({i, j + 1, 0});
      }
      dist[i][j] = INF;
    }
  }
  dist[0][0] = 0;
  deque<vector<int> > q;
  q.push_front({0, 0});
  for (int i = 0; i < (int)m; i++) {
    int a, b;
    cin >> a >> b;
    a -= 1;
    b -= 1;
    adj2[a][0].push_back({b, 0, 0, 1});
    adj2[b][1].push_back({a, 1, 0, 1});
    for (int j = 0; j < (int)lg + 1; j++) {
      if (j % 2 == 0)
        adj[a][j].push_back({b, j, 1});
      else
        adj[b][j].push_back({a, j, 1});
    }
  }
  while (q.size()) {
    vector<int> curr = q.front();
    q.pop_front();
    int d = dist[curr[0]][curr[1]];
    for (auto p : adj[curr[0]][curr[1]]) {
      if (dist[p[0]][p[1]] > d + p[2]) {
        dist[p[0]][p[1]] = d + p[2];
        if (p[2])
          q.push_back({p[0], p[1]});
        else
          q.push_front({p[0], p[1]});
      }
    }
  }
  long long ans = LONG_LONG_MAX;
  for (int j = 0; j < (int)lg + 1; j++)
    if (dist[n - 1][j] != INF) {
      ans = min(ans, (dist[n - 1][j] + (1 << j) - 1) % mod);
    }
  if (ans != LONG_LONG_MAX) {
    cout << ans << '\n';
    return 0;
  }
  dist2[0][0] = {0, 0};
  q.push_back({0, 0});
  while (q.size()) {
    vector<int> curr = q.front();
    q.pop_front();
    pair<int, int> d = dist2[curr[0]][curr[1]];
    for (auto p : adj2[curr[0]][curr[1]]) {
      if (dist2[p[0]][p[1]] >
          (pair<int, int>){d.first + p[2], d.second + p[3]}) {
        dist2[p[0]][p[1]] = {d.first + p[2], d.second + p[3]};
        if (p[2])
          q.push_back({p[0], p[1]});
        else
          q.push_front({p[0], p[1]});
      }
    }
  }
  pair<long long, long long> fin = min(dist2[n - 1][0], dist2[n - 1][1]);
  cout << (fin.second + (modpow(2, fin.first, mod) - 1 + mod)) % mod << '\n';
  return 0;
}
