#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
const long long maxn = 2e5 + 10;
inline long long read() {
  long long ret = 0;
  long long f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -f;
    ch = getchar();
  }
  while (ch <= '9' && ch >= '0') {
    ret = ret * 10 + (ch ^ '0');
    ch = getchar();
  }
  return f * ret;
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
long long n, m;
long long dis[19][maxn];
vector<long long> e[20][maxn];
void add(long long u, long long v, long long c) { e[c][u].push_back(v); }
struct node {
  long long c, u;
};
queue<node> q;
long long vis[20][maxn];
long long spfa() {
  memset(dis, 0x3f, sizeof(dis));
  q.push((node){0, 1});
  dis[0][1] = 0;
  while (!q.empty()) {
    long long u = q.front().u;
    long long c = q.front().c;
    q.pop();
    vis[c][u] = 0;
    for (long long v : e[c & 1][u]) {
      if (dis[c][v] > dis[c][u] + 1) {
        dis[c][v] = dis[c][u] + 1;
        if (!vis[c][v]) vis[c][v] = 1, q.push((node){c, v});
      }
    }
    if (c < 18) {
      if (dis[c + 1][u] > dis[c][u] + (1 << c)) {
        dis[c + 1][u] = dis[c][u] + (1 << c);
        if (!vis[c + 1][u]) {
          vis[c + 1][u] = 1;
          q.push((node){c + 1, u});
        }
      }
    }
  }
  long long res = 0x3f3f3f3f;
  for (long long i = 0; i <= 18; i++) {
    res = min(res, dis[i][n]);
  }
  return res;
}
inline long long power(long long t, long long x) {
  long long res = 1;
  for (; x; x >>= 1)
    x & 1 ? (res = 1ll * res * t % mod) : 1, t = 1ll * t * t % mod;
  return res;
}
long long diss[maxn];
signed main() {
  long long x, y;
  n = read(), m = read();
  for (long long i = 1; i <= m; ++i) {
    x = read(), y = read();
    add(x, y, 0), add(y, x, 1);
  }
  long long ans = spfa();
  if (ans < 1e9) return write(ans), 0;
  memset(diss, 63, sizeof(diss));
  queue<long long> qq, tmp;
  diss[1] = 0, qq.push(1), tmp.push(1);
  for (long long k = 0;; ++k) {
    while (!qq.empty()) {
      long long u = qq.front();
      qq.pop();
      if (u == n) return write((power(2, k) - 1 + diss[u]) % mod), 0;
      for (long long v : e[k & 1][u])
        if (diss[v] > diss[u] + 1)
          diss[v] = diss[u] + 1, qq.push(v), tmp.push(v);
    }
    while (!tmp.empty()) qq.push(tmp.front()), tmp.pop();
  }
  return 0;
}
