#include <bits/stdc++.h>
using namespace std;
const int MN = 2e5 + 5;
const int INF = 2e9;
const int mod = 998244353;
int N, M, res;
vector<int> E[2][MN];
int dp[MN][19], inq[MN][19], dis[MN], two[MN];
queue<pair<int, int> > q;
inline void AddEdge(int u, int v, int type) {
  E[type][u].push_back(v);
  return;
}
inline void chkmin(int &x, int y) { x = min(x, y); }
inline void sssp() {
  for (int i = 1; i <= N; ++i)
    for (int j = 0; j <= 18; ++j) dp[i][j] = INF;
  dp[1][0] = 0;
  q.push(make_pair(1, 0));
  while (!q.empty()) {
    int u = q.front().first, k = q.front().second;
    q.pop();
    inq[u][k] = false;
    for (auto v : E[k & 1][u]) {
      if (dp[u][k] + 1 < dp[v][k]) {
        dp[v][k] = dp[u][k] + 1;
        if (!inq[v][k]) {
          inq[v][k] = true;
          q.push(make_pair(v, k));
        }
      }
    }
    if (k < 18 && dp[u][k] + (1 << k) < dp[u][k + 1]) {
      dp[u][k + 1] = dp[u][k] + (1 << k);
      if (!inq[u][k + 1]) {
        inq[u][k + 1] = true;
        q.push(make_pair(u, k + 1));
      }
    }
  }
  for (int i = 0; i <= 18; ++i) chkmin(res, dp[N][i]);
}
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= M; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    AddEdge(u, v, 0), AddEdge(v, u, 1);
  }
  res = INF;
  sssp();
  if (res < INF) {
    printf("%d\n", res);
    return 0;
  }
  for (int i = 1; i <= N; ++i) dis[i] = INF;
  two[0] = 1;
  for (int i = 1; i <= N; ++i) two[i] = 2ll * two[i - 1] % mod;
  queue<int> q, qq;
  q.push(1);
  dis[1] = 0;
  qq.push(1);
  for (int k = 0;; ++k) {
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      if (u == N) {
        printf("%d\n", 1LL * ((dis[u] + two[k] - 1) % mod + mod) % mod);
        return 0;
      }
      for (int v : E[k & 1][u])
        if (dis[u] + 1 < dis[v]) {
          dis[v] = dis[u] + 1;
          q.push(v);
          qq.push(v);
        }
    }
    while (!qq.empty()) {
      q.push(qq.front());
      qq.pop();
    }
  }
  printf("%d\n", dis[N]);
  return 0;
}
