#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
const int N = 2e5 + 2, mod = 998244353;
int n, m, d[N][20];
pair<int, int> dist[N][2];
vector<int> g[2][N];
struct State {
  int d, ver, B;
  bool operator<(const State& oth) const { return d > oth.d; }
};
struct State1 {
  int B, A, ver;
  bool operator<(const State1& oth) const {
    return B > oth.B || (B == oth.B && A > oth.A);
  }
};
void solve1() {
  priority_queue<State1> pq;
  for (int i = (1); i <= (n); ++i) dist[i][0] = dist[i][1] = {1e9, 1e9};
  dist[1][0] = {0, 0};
  pq.push({0, 0, 1});
  while (!pq.empty()) {
    State1 cur = pq.top();
    pq.pop();
    int side = cur.B & 1;
    if (pair<int, int>(cur.B, cur.A) != dist[cur.ver][side]) continue;
    for (int v : g[side][cur.ver])
      if (dist[v][side].first > cur.B ||
          (dist[v][side].first == cur.B && dist[v][side].second > cur.A + 1)) {
        dist[v][side] = {cur.B, cur.A + 1};
        pq.push({cur.B, cur.A + 1, v});
      }
    if (dist[cur.ver][side ^ 1].first > cur.B + 1 ||
        (dist[cur.ver][side ^ 1].first == cur.B + 1 &&
         dist[cur.ver][side ^ 1].second > cur.A)) {
      dist[cur.ver][side ^ 1] = {cur.B + 1, cur.A};
      pq.push({cur.B + 1, cur.A, cur.ver});
    }
  }
  pair<int, int> ans = dist[n][0];
  if (dist[n][1].first < ans.first ||
      (dist[n][1].first == ans.first && dist[n][1].second < ans.second))
    ans = dist[n][1];
  assert(ans.first != 1e9 && ans.second != 1e9);
  int res = 1;
  for (int i = (1); i <= (ans.first); ++i) res = res * 2LL % mod;
  cout << (res + ans.second - 1) % mod;
}
void solve() {
  int LG = 32 - __builtin_clz(m);
  assert(LG <= 19);
  priority_queue<State> pq;
  pq.push({0, 1, 0});
  for (int i = (1); i <= (n); ++i)
    for (int j = (0); j <= (19); ++j) d[i][j] = 1e9;
  d[1][0] = 0;
  while (!pq.empty()) {
    State cur = pq.top();
    pq.pop();
    if (cur.d != d[cur.ver][cur.B]) continue;
    for (int v : g[cur.B & 1][cur.ver])
      if (d[v][cur.B] > cur.d + 1) {
        d[v][cur.B] = cur.d + 1;
        pq.push({d[v][cur.B], v, cur.B});
      }
    if (cur.B < LG) {
      if (d[cur.ver][cur.B + 1] > cur.d + (1 << cur.B)) {
        d[cur.ver][cur.B + 1] = cur.d + (1 << cur.B);
        pq.push({d[cur.ver][cur.B + 1], cur.ver, cur.B + 1});
      }
    }
  }
  int ans = 1e9;
  for (int i = (0); i <= (LG); ++i)
    if (ans > d[n][i]) ans = d[n][i];
  if (ans == 1e9)
    solve1();
  else
    cout << ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  for (int i = (1); i <= (m); ++i) {
    int u, v;
    cin >> u >> v;
    g[0][u].emplace_back(v);
    g[1][v].emplace_back(u);
  }
  solve();
  return 0;
}
