#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
int n, m, x, y;
vector<int> e[2][N];
inline void adde(int x, int y, int o) { e[o][x].push_back(y); }
inline int read() {
  char ch = getchar();
  int x = 0, f = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 1) + (x << 3) - '0' + ch;
    ch = getchar();
  }
  return x * f;
}
void write(int x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
  return;
}
int dis[19][N];
bool vis[19][N];
queue<pair<int, int> > q;
int spfa() {
  memset(dis, 63, sizeof(dis));
  q.push(pair<int, int>(0, 1));
  dis[0][1] = 0;
  while (!q.empty()) {
    int u = q.front().second, k = q.front().first;
    q.pop();
    vis[k][u] = 0;
    for (int v : e[k & 1][u]) {
      if (dis[k][v] > dis[k][u] + 1) {
        dis[k][v] = dis[k][u] + 1;
        if (!vis[k][v]) vis[k][v] = 1, q.push(pair<int, int>(k, v));
      }
    }
    if (k < 18) {
      if (dis[k + 1][u] > dis[k][u] + (1 << k)) {
        dis[k + 1][u] = dis[k][u] + (1 << k);
        if (!vis[k + 1][u]) vis[k + 1][u] = 1, q.push(pair<int, int>(k + 1, u));
      }
    }
  }
  int res = 1e9 + 7;
  for (int i = 0; i <= 18; ++i) res = min(res, dis[i][n]);
  return res;
}
queue<int> Q, tmp;
int diss[N];
inline int qbit(int x) {
  int res = 1, t = 2;
  for (; x; x >>= 1)
    x & 1 ? (res = 1ll * res * t % mod) : 1, t = 1ll * t * t % mod;
  return res;
}
int main() {
  n = read(), m = read();
  for (int i = 1; i <= m; ++i) {
    x = read(), y = read();
    adde(x, y, 0), adde(y, x, 1);
  }
  int ans = spfa();
  if (ans < 1e9) return write(ans), 0;
  memset(diss, 63, sizeof(diss));
  diss[1] = 0, Q.push(1), tmp.push(1);
  for (int k = 0;; ++k) {
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      if (u == n) return write((qbit(k) - 1 + diss[u]) % mod), 0;
      for (int v : e[k & 1][u])
        if (diss[v] > diss[u] + 1)
          diss[v] = diss[u] + 1, Q.push(v), tmp.push(v);
    }
    while (!tmp.empty()) Q.push(tmp.front()), tmp.pop();
  }
}
