#include <bits/stdc++.h>
using namespace std;
const int INF = 1012345678;
const long long MOD = 998244353;
vector<int> AdjList[200005][2];
pair<int, int> dist1[200005][2];
int dist2[200005][21];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    AdjList[u][0].push_back(v);
    AdjList[v][1].push_back(u);
  }
  for (int i = 1; i <= n; i++) {
    dist1[i][0] = pair<int, int>(INF, INF);
    dist1[i][1] = pair<int, int>(INF, INF);
  }
  dist1[1][0] = pair<int, int>(0, 0);
  priority_queue<pair<pair<int, int>, pair<int, int> >,
                 vector<pair<pair<int, int>, pair<int, int> > >,
                 greater<pair<pair<int, int>, pair<int, int> > > >
      pq;
  pq.push(
      pair<pair<int, int>, pair<int, int> >(dist1[1][0], pair<int, int>(1, 0)));
  while (!pq.empty()) {
    pair<pair<int, int>, pair<int, int> > temp = pq.top();
    pq.pop();
    pair<int, int> d = temp.first;
    pair<int, int> u2 = temp.second;
    int u = u2.first;
    int flips = u2.second;
    if (d > dist1[u][flips]) {
      continue;
    }
    for (int v : AdjList[u][flips]) {
      pair<int, int> nextDist =
          pair<int, int>(dist1[u][flips].first, dist1[u][flips].second + 1);
      if (nextDist < dist1[v][flips]) {
        dist1[v][flips] = nextDist;
        pq.push(pair<pair<int, int>, pair<int, int> >(
            dist1[v][flips], pair<int, int>(v, flips)));
      }
    }
    for (int v : AdjList[u][flips ^ 1]) {
      pair<int, int> nextDist =
          pair<int, int>(dist1[u][flips].first + 1, dist1[u][flips].second + 1);
      if (nextDist < dist1[v][flips ^ 1]) {
        dist1[v][flips ^ 1] = nextDist;
        pq.push(pair<pair<int, int>, pair<int, int> >(
            dist1[v][flips ^ 1], pair<int, int>(v, flips ^ 1)));
      }
    }
  }
  pair<int, int> temp = min(dist1[n][0], dist1[n][1]);
  if (temp.first >= 20) {
    int k = temp.first;
    long long ans = 1;
    while (k > 0) {
      ans = (ans * 2) % MOD;
      k--;
    }
    ans = (ans + temp.second + MOD - 1) % MOD;
    printf("%lld", ans);
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    for (int k = 0; k <= 20; k++) {
      dist2[i][k] = INF;
    }
  }
  dist2[1][0] = 0;
  priority_queue<pair<int, pair<int, int> >,
                 vector<pair<int, pair<int, int> > >,
                 greater<pair<int, pair<int, int> > > >
      pq2;
  pq2.push(pair<int, pair<int, int> >(dist2[1][0], pair<int, int>(1, 0)));
  while (!pq2.empty()) {
    pair<int, pair<int, int> > temp = pq2.top();
    pq2.pop();
    int d = temp.first;
    pair<int, int> u2 = temp.second;
    int u = u2.first;
    int flips = u2.second;
    if (d > dist2[u][flips]) {
      continue;
    }
    for (int v : AdjList[u][flips & 1]) {
      int nextDist = dist2[u][flips] + 1;
      if (nextDist < dist2[v][flips]) {
        dist2[v][flips] = nextDist;
        pq2.push(pair<int, pair<int, int> >(dist2[v][flips],
                                            pair<int, int>(v, flips)));
      }
    }
    for (int v : AdjList[u][(flips & 1) ^ 1]) {
      if (flips == 20) {
        break;
      }
      int nextDist = dist2[u][flips] + 1 + (1 << flips);
      if (nextDist < dist2[v][flips + 1]) {
        dist2[v][flips + 1] = nextDist;
        pq2.push(pair<int, pair<int, int> >(dist2[v][flips + 1],
                                            pair<int, int>(v, flips + 1)));
      }
    }
  }
  int ans = INF;
  for (int i = 0; i <= 20; i++) {
    ans = min(ans, dist2[n][i]);
  }
  if (ans == INF) {
    throw;
  }
  printf("%d", ans);
  return 0;
}
