#include <bits/stdc++.h>
using namespace std;
using Int = long long;
template <class T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;
const Int MOD = 998244353;
Int modpow(Int x, Int y) {
  if (y == 0) return 1;
  if (y % 2 == 0) return modpow(x * x % MOD, y / 2);
  return x * modpow(x, y - 1) % MOD;
}
pair<int, int> min_pair(pair<int, int> x, pair<int, int> y) {
  if (x.first < 0) return y;
  if (y.first < 0) return x;
  if (x.first == y.first) return min(x, y);
  if (x.first < y.first) swap(x, y);
  assert(x.first > y.first);
  if (x.first >= 30) return y;
  Int tmp = ((1LL << x.first) + x.second) - ((1LL << y.first) + y.second);
  return tmp < 0 ? x : y;
}
int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<int>> G(N), R(N);
  for (int i = 0; i < M; i++) {
    int U, V;
    cin >> U >> V;
    U--, V--;
    G[U].push_back(V);
    R[V].push_back(U);
  }
  vector<int> nodes = {0};
  vector<int> total_moves(N, 1e9);
  pair<int, int> ans = {-1, -1};
  total_moves[0] = 0;
  int k = 0;
  MinHeap<pair<int, int>> Q, QQ;
  Q.emplace(0, 0);
  QQ.emplace(0, 0);
  while (!Q.empty()) {
    while (!Q.empty()) {
      auto [mv, n] = Q.top();
      Q.pop();
      if (total_moves[n] != mv) continue;
      if (n == N - 1) ans = min_pair(ans, make_pair(k, mv));
      for (int m : G[n]) {
        if (total_moves[m] > mv + 1) {
          total_moves[m] = mv + 1;
          Q.emplace(mv + 1, m);
          QQ.emplace(mv + 1, m);
        }
      }
    }
    swap(G, R);
    swap(Q, QQ);
    k++;
  }
  cout << (ans.second + modpow(2, ans.first) + MOD - 1) % MOD << '\n';
  return 0;
}
