#include <bits/stdc++.h>
using namespace std;
template <class T>
T fp(T x, long long e) {
  T ans(1);
  for (; e > 0; e /= 2) {
    if (e & 1) ans = ans * x;
    x = x * x;
  }
  return ans;
}
const long long mod = 998244353;
struct mb {
  mb(int v = 0) : val(v < 0 ? v + mod : v) {}
  mb(long long v) { val = (v % mod + mod) % mod; }
  int val;
  void operator+=(mb o) { *this = *this + o; }
  void operator-=(mb o) { *this = *this - o; }
  void operator*=(mb o) { *this = *this * o; }
  mb operator*(mb o) { return (int)((long long)val * o.val % mod); }
  mb operator+(mb o) {
    return val + o.val >= mod ? val + o.val - mod : val + o.val;
  }
  mb operator-(mb o) {
    return val - o.val < 0 ? val - o.val + mod : val - o.val;
  }
};
const int N = 1e6 + 10;
vector<int> gd[N], gr[N];
int n, m;
pair<long long, long long> dijpar() {
  priority_queue<tuple<long long, long long, long long, long long>,
                 vector<tuple<long long, long long, long long, long long>>,
                 greater<tuple<long long, long long, long long, long long>>>
      pq;
  pq.emplace(0, 0, 0, 0);
  vector<vector<int>> vis(n, vector<int>(2));
  while (!pq.empty()) {
    long long kac, dac, par, no;
    tie(kac, dac, par, no) = pq.top();
    pq.pop();
    if (vis[no][par]) continue;
    vis[no][par] = 1;
    if (no == n - 1) {
      return {kac, dac};
    }
    vector<int> *g;
    if (kac % 2 == 0)
      g = gd;
    else
      g = gr;
    for (auto &it : g[no]) {
      pq.emplace(kac, dac + 1, par, it);
    }
    pq.emplace(kac + 1, dac, !par, no);
  }
}
long long dijsoma(long long mink) {
  vector<vector<int>> vis(n, vector<int>(mink));
  priority_queue<tuple<long long, long long, long long>,
                 vector<tuple<long long, long long, long long>>,
                 greater<tuple<long long, long long, long long>>>
      pq;
  pq.emplace(0, 0, 0);
  vector<vector<long long>> dist(n, vector<long long>(mink, LLONG_MAX));
  while (!pq.empty()) {
    long long dac, kac, no;
    tie(dac, kac, no) = pq.top();
    pq.pop();
    if (vis[no][kac]) continue;
    if (no == n - 1) return dac;
    vis[no][kac] = 1;
    dist[no][kac] = dac;
    vector<int> *g;
    if (kac % 2 == 0)
      g = gd;
    else
      g = gr;
    for (auto &it : g[no]) {
      pq.emplace(dac + 1, kac, it);
    }
    if (kac + 1 < mink) pq.emplace(dac + (1ll << (kac)), kac + 1, no);
  }
  long long ans = LLONG_MAX;
  for (int i = 0; i < mink; i++) ans = min<long long>(ans, dist[n - 1][i]);
  return ans;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    gd[u].push_back(v);
    gr[v].push_back(u);
  }
  long long mink, dist;
  tie(mink, dist) = dijpar();
  if (mink <= 30) {
    long long ans = dijsoma(35);
    cout << ans % mod << "\n";
    return 0;
  }
  mb ans = dist;
  mb add = 1;
  for (int cnt = 0; cnt < mink; cnt++) {
    ans += add;
    add *= 2;
  }
  cout << ans.val << "\n";
}
