#include <bits/stdc++.h>
using namespace std;
const int N = 200004;
const int mod = 998244353;
pair<int, int> dp[N][2];
int SP[N][20];
vector<int> g[N][2];
priority_queue<pair<pair<int, int>, pair<int, int> > > bfs;
priority_queue<pair<int, pair<int, int> > > sp;
void solve() {
  int n, m;
  cin >> n >> m;
  for (int i = (1); i <= (m); ++i) {
    int a, b;
    cin >> a >> b;
    g[a][0].push_back(b);
    g[b][1].push_back(a);
  }
  for (int i = (1); i <= (n); ++i) {
    for (int j = (0); j <= (1); ++j)
      dp[i][j] = pair<int, int>(1 << 30, 1 << 30);
  }
  dp[1][0] = pair<int, int>(0, 0);
  bfs.push(make_pair(pair<int, int>(0, 0), pair<int, int>(1, 0)));
  while (!bfs.empty()) {
    pair<int, int> U = bfs.top().second;
    pair<int, int> w = bfs.top().first;
    bfs.pop();
    int u = U.first;
    int st = U.second;
    w.first = -w.first;
    w.second = -w.second;
    if (dp[u][st ^ 1] > pair<int, int>(w.first + 1, w.second)) {
      dp[u][st ^ 1] = pair<int, int>(w.first + 1, w.second);
      bfs.push(make_pair(pair<int, int>(-w.first - 1, -w.second),
                         pair<int, int>(u, st ^ 1)));
    }
    for (int e : g[u][st]) {
      if (dp[e][st] > pair<int, int>(w.first, w.second + 1)) {
        dp[e][st] = pair<int, int>(w.first, w.second + 1);
        bfs.push(make_pair(pair<int, int>(-w.first, -w.second - 1),
                           pair<int, int>(e, st)));
      }
    }
  }
  pair<int, int> ans = min(dp[n][0], dp[n][1]);
  if (ans.first > 19) {
    int sol = 1;
    for (int i = (1); i <= (ans.first); ++i) sol = (sol << 1) % mod;
    if (ans.first == 0)
      sol = 0;
    else
      sol = (sol + mod - 1) % mod;
    cout << (sol + ans.second) % mod;
    return;
  }
  for (int i = (1); i <= (n); ++i) {
    for (int j = (0); j <= (19); ++j) SP[i][j] = SP[i][j] = (1 << 30);
  }
  SP[1][0] = 0;
  sp.push(make_pair(0, pair<int, int>(1, 0)));
  while (!sp.empty()) {
    int u = sp.top().second.first;
    int st = sp.top().second.second;
    int w = -sp.top().first;
    sp.pop();
    if (st < 19 && SP[u][st + 1] > w + (1 << st)) {
      SP[u][st + 1] = w + (1 << st);
      sp.push(make_pair(-SP[u][st + 1], pair<int, int>(u, st + 1)));
    }
    for (int e : g[u][st & 1]) {
      if (SP[e][st] > w + 1) {
        SP[e][st] = w + 1;
        sp.push(make_pair(-SP[e][st], pair<int, int>(e, st)));
      }
    }
  }
  int ANS = (1 << 30);
  for (int i = (0); i <= (19); ++i) {
    ANS = min(ANS, SP[n][i]);
  }
  cout << ANS;
}
int main() {
  int t;
  solve();
  return 0;
}
