#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e6 + 5, mod = 998244353;
vector<pair<int, int> > adj[mxN];
int n, m, d[mxN][22];
bool was[mxN][22];
pair<int, int> D[mxN][2];
int main() {
  ios ::sync_with_stdio(false), cin.tie(nullptr);
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back({v, 1});
    adj[v].push_back({u, 2});
  }
  int ans = mod;
  {
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j <= 20; ++j) d[i][j] = mod;
    }
    queue<pair<int, int> > q;
    d[1][0] = 0;
    was[1][0] = 1;
    q.push({1, 0});
    while (!q.empty()) {
      int v = q.front().first;
      int now = q.front().second;
      q.pop();
      for (auto to : adj[v]) {
        if (to.second == 1) {
          if (now & 1) {
            if (now < 20 && !was[to.first][now + 1]) {
              d[to.first][now + 1] = d[v][now] + 1;
              q.push({to.first, now + 1});
              was[to.first][now + 1] = 1;
            }
          } else {
            if (!was[to.first][now]) {
              d[to.first][now] = d[v][now] + 1;
              q.push({to.first, now});
              was[to.first][now] = 1;
            }
          }
        } else {
          if (now % 2 == 0) {
            if (now < 20 && !was[to.first][now + 1]) {
              d[to.first][now + 1] = d[v][now] + 1;
              q.push({to.first, now + 1});
              was[to.first][now + 1] = 1;
            }
          } else {
            if (!was[to.first][now]) {
              d[to.first][now] = d[v][now] + 1;
              q.push({to.first, now});
              was[to.first][now] = 1;
            }
          }
        }
      }
    }
    for (int i = 0; i <= 20; ++i) ans = min(ans, ((1 << i) - 1) + d[n][i]);
    if (ans != mod) {
      cout << ans;
      return 0;
    }
  }
  {
    for (int i = 1; i <= n; ++i) D[i][0] = D[i][1] = {mod, mod};
    set<pair<pair<pair<int, int>, int>, int> > st;
    st.insert({{{0, 0}, 0}, 1});
    D[1][0] = {0, 0};
    while (!st.empty()) {
      pair<int, int> len = st.begin()->first.first;
      int rev = st.begin()->first.second;
      int v = st.begin()->second;
      st.erase(st.begin());
      for (auto to : adj[v]) {
        if (to.second == 1) {
          if (!rev) {
            if (D[to.first][0] > make_pair(len.first, len.second + 1)) {
              st.erase({{D[to.first][0], 0}, to.first});
              D[to.first][0] = {len.first, len.second + 1};
              st.insert({{D[to.first][0], 0}, to.first});
            }
          } else {
            if (D[to.first][0] > make_pair(len.first + 1, len.second + 1)) {
              st.erase({{D[to.first][0], 0}, to.first});
              D[to.first][0] = {len.first + 1, len.second + 1};
              st.insert({{D[to.first][0], 0}, to.first});
            }
          }
        } else {
          if (!rev) {
            if (D[to.first][1] > make_pair(len.first + 1, len.second + 1)) {
              st.erase({{D[to.first][1], 1}, to.first});
              D[to.first][1] = {len.first + 1, len.second + 1};
              st.insert({{D[to.first][1], 1}, to.first});
            }
          } else {
            if (D[to.first][1] > make_pair(len.first, len.second + 1)) {
              st.erase({{D[to.first][1], 1}, to.first});
              D[to.first][1] = {len.first, len.second + 1};
              st.insert({{D[to.first][1], 1}, to.first});
            }
          }
        }
      }
    }
    ans = 1;
    pair<int, int> best = min(D[n][0], D[n][1]);
    int mult = 1;
    for (int i = 2; i <= best.first; ++i)
      mult = mult * 2 % mod, ans = (ans + mult) % mod;
    ans = (ans + best.second) % mod;
  }
  cout << ans;
  return 0;
}
