#include <bits/stdc++.h>
using namespace std;
const int M = 998244353;
int power(int a, int p) {
  if (p == 0) return 1;
  int ans = power(a, p / 2);
  ans = (1LL * ans * ans) % M;
  if (p % 2) ans = (1LL * ans * a) % M;
  return ans;
}
const int N = 2e5 + 7, K = 14;
vector<int> adj[N], adjr[N];
pair<int, int> dis[N][K + 2];
pair<int, int> INF = {1e9, 1e9};
int eval(pair<int, int> a) {
  int ans = a.second;
  ans = (ans + power(2, a.first) - 1) % M;
  return ans;
}
pair<int, int> best(pair<int, int> a, pair<int, int> b) {
  if (a.first >= K || b.first >= K) {
    if (a < b)
      return a;
    else
      return b;
  } else {
    if (eval(a) < eval(b))
      return a;
    else
      return b;
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adjr[v].push_back(u);
  }
  for (int i = 0; i < N; i++) fill(dis[i], dis[i] + K + 2, INF);
  dis[1][0] = {0, 0};
  priority_queue<pair<pair<int, int>, pair<int, int>>,
                 vector<pair<pair<int, int>, pair<int, int>>>,
                 greater<pair<pair<int, int>, pair<int, int>>>>
      pq;
  pq.push({dis[1][0], {1, 0}});
  while (pq.size()) {
    pair<int, int> dd = pq.top().first;
    int u = pq.top().second.first;
    int k = pq.top().second.second;
    pq.pop();
    if (dd > dis[u][k]) continue;
    for (int v : adj[u]) {
      pair<int, int> nw = dd;
      int nk = k;
      if (nk % 2) nk++, nw.first++;
      nw.second++;
      if (nk == K + 2) nk = K;
      if (dis[v][nk] > nw) {
        dis[v][nk] = nw;
        pq.push({nw, {v, nk}});
      }
    }
    for (int v : adjr[u]) {
      pair<int, int> nw = dd;
      int nk = k;
      if (nk % 2 == 0) nk++, nw.first++;
      nw.second++;
      if (nk == K + 2) nk = K;
      if (dis[v][nk] > nw) {
        dis[v][nk] = nw;
        pq.push({nw, {v, nk}});
      }
    }
  }
  pair<int, int> ans = INF;
  for (int i = 0; i < K + 2; i++) {
    ans = best(ans, dis[n][i]);
  }
  cout << eval(ans) << endl;
}
