#include <bits/stdc++.h>
const long long mod = 998244353;
const int N = 2e5 + 100, LG = 20;
std::vector<int> g[2][N];
long long answ = 0;
long long dp[N][LG][2];
long long d[N][2];
long long n, m;
long long INF;
long long get(long long x) { return (1LL << x) - 1; }
struct pos {
  long long cost;
  int i;
  int t;
  friend bool operator<(pos a, pos b) {
    if (a.cost == b.cost) {
      if (a.i == b.i) return a.t < b.t;
      return a.i < b.i;
    }
    return a.cost < b.cost;
  }
};
bool solve1() {
  memset(dp, 0x3f, sizeof(dp));
  INF = dp[0][0][0];
  dp[0][0][0] = 0;
  for (int lg = 0; lg < LG - 1; ++lg) {
    std::set<pos> q;
    for (int v = 0; v < (int)(n); ++v) {
      for (int t = 0; t < (int)(2); ++t) {
        q.insert({dp[v][lg][t], v, t});
      }
    }
    while (!q.empty()) {
      auto v = *q.begin();
      q.erase(q.begin());
      for (auto to : g[v.t][v.i]) {
        if (dp[to][lg][v.t] > v.cost + 1) {
          q.erase({dp[to][lg][v.t], to, v.t});
          dp[to][lg][v.t] = v.cost + 1;
          q.insert({dp[to][lg][v.t], to, v.t});
        }
      }
    }
    for (int v = 0; v < (int)(n); ++v) {
      for (int t = 0; t < 2; ++t) {
        dp[v][lg + 1][t ^ 1] = std::min(dp[v][lg + 1][t ^ 1], dp[v][lg][t]);
      }
    }
  }
  long long minAnsw = INF;
  for (int lg = 0; lg < (int)(LG); ++lg) {
    for (int t = 0; t < (int)(2); ++t) {
      minAnsw = std::min(minAnsw, get(lg) + dp[n - 1][lg][t]);
    }
  }
  if (minAnsw >= INF) return false;
  answ = minAnsw % mod;
  return 1;
}
long long bin_p(long long a, long long b) {
  if (!b) return 1;
  if (b % 2 == 0) {
    long long cur = bin_p(a, b / 2);
    return cur * cur % mod;
  } else {
    return a * bin_p(a, b - 1) % mod;
  }
}
const long long BORDER = 1e12;
void solve2() {
  memset(d, 0x3f, sizeof(d));
  d[0][0] = 0;
  std::set<pos> q;
  q.insert({d[0][0], 0, 0});
  while (!q.empty()) {
    auto v = *q.begin();
    q.erase(q.begin());
    for (auto to : g[v.t][v.i]) {
      if (d[to][v.t] > v.cost + 1) {
        q.erase({d[to][v.t], to, v.t});
        d[to][v.t] = v.cost + 1;
        q.insert({d[to][v.t], to, v.t});
      }
    }
    if (d[v.i][v.t ^ 1] > v.cost + BORDER) {
      q.erase({d[v.i][v.t ^ 1], v.i, v.t ^ 1});
      d[v.i][v.t ^ 1] = v.cost + BORDER;
      q.insert({d[v.i][v.t ^ 1], v.i, v.t ^ 1});
    }
  }
  long long answ = std::min(d[n - 1][0], d[n - 1][1]);
  long long rev = answ / BORDER, rev2 = answ % BORDER;
  long long realAnsw = (bin_p(2, rev) - 1) + rev2;
  realAnsw = (realAnsw % mod + mod) % mod;
  std::cout << realAnsw;
}
signed main() {
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(0);
  std::cin >> n >> m;
  for (int i = 0; i < (int)(m); ++i) {
    int a, b;
    std::cin >> a >> b;
    --a;
    --b;
    g[0][a].push_back(b);
    g[1][b].push_back(a);
  }
  if (solve1()) {
    std::cout << answ;
  } else {
    solve2();
  }
}
