#include <bits/stdc++.h>
using namespace std;
template <typename T>
void read(T &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= f;
}
inline void write(int x) {
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
const int N = 400005, P = 998244353;
inline int power(int x, int y) {
  static int r;
  r = 1;
  while (y) {
    if (y & 1) r = (long long)r * x % P;
    x = (long long)x * x % P;
    y >>= 1;
  }
  return r;
}
int n;
vector<int> G0[N], G1[N];
inline void add0(int x, int y) { G0[x].push_back(y); }
inline void add1(int x, int y) { G1[x].push_back(y); }
inline void init() {
  int i, x, y, m;
  for (i = 1; i <= n; ++i) add1(i, i + n), add1(i + n, i);
  read(m);
  while (m--) read(x), read(y), add0(x, y), add0(y + n, x + n);
}
int d1[N];
deque<int> q;
inline void getd1() {
  int i, x, y;
  while (!q.empty()) q.pop_front();
  for (i = 1; i <= n << 1; ++i) d1[i] = 99999999;
  d1[1] = 0;
  q.push_back(1);
  while (!q.empty()) {
    x = q.front(), q.pop_front();
    for (i = 0; i < G0[x].size(); ++i) {
      y = G0[x][i];
      if (d1[y] > d1[x]) d1[y] = d1[x], q.push_front(y);
    }
    for (i = 0; i < G1[x].size(); ++i) {
      y = G1[x][i];
      if (d1[y] > d1[x] + 1) d1[y] = d1[x] + 1, q.push_back(y);
    }
  }
}
int ans;
int d2[N];
inline void getd2() {
  int i, x, y;
  while (!q.empty()) q.pop_front();
  for (i = 1; i <= n << 1; ++i) d2[i] = 99999999;
  d2[1] = 0;
  q.push_back(1);
  while (!q.empty()) {
    x = q.front(), q.pop_front();
    for (i = 0; i < G1[x].size(); ++i) {
      y = G1[x][i];
      if (d1[y] == d1[x] + 1) {
        if (d2[y] > d2[x]) d2[y] = d2[x], q.push_front(y);
      }
    }
    for (i = 0; i < G0[x].size(); ++i) {
      y = G0[x][i];
      if (d1[y] == d1[x]) {
        if (d2[y] > d2[x] + 1) d2[y] = d2[x] + 1, q.push_back(y);
      }
    }
  }
}
int dis[N][20];
int Qx[N * 40], Qt[N * 40];
int ql, qr;
inline void work() {
  int i, j, x, y, t, nt;
  for (i = 1; i <= n << 1; ++i)
    for (j = 0; j < 20; ++j) dis[i][j] = 99999999;
  ql = n * 40 + 5, qr = ql - 1;
  dis[1][0] = 0;
  ++qr;
  Qx[qr] = 1, Qt[qr] = 0;
  while (ql <= qr) {
    x = Qx[ql], t = Qt[ql];
    ++ql;
    for (i = 0; i < G1[x].size(); ++i) {
      y = G1[x][i], nt = t + 1;
      if (nt >= 20) continue;
      if (dis[y][nt] > dis[x][t]) {
        dis[y][nt] = dis[x][t];
        --ql;
        Qx[ql] = y, Qt[ql] = nt;
      }
    }
    for (i = 0; i < G0[x].size(); ++i) {
      y = G0[x][i], nt = t;
      if (nt >= 20) continue;
      if (dis[y][nt] > dis[x][t] + 1) {
        dis[y][nt] = dis[x][t] + 1;
        ++qr;
        Qx[qr] = y, Qt[qr] = nt;
      }
    }
  }
  for (i = 0; i < 20; ++i) ans = min(ans, dis[n][i] + (1 << i) - 1);
  for (i = 0; i < 20; ++i) ans = min(ans, dis[n << 1][i] + (1 << i) - 1);
}
inline void solve() {
  read(n);
  init();
  if (n == 1) {
    cout << 0 << '\n';
    return;
  }
  getd1();
  int dd1 = min(d1[n], d1[n << 1]);
  if (dd1 >= 20) {
    getd2();
    int ans = (power(2, dd1) - 1 + P) % P;
    if (d1[n << 1] != dd1)
      ans = (ans + d2[n]) % P;
    else if (d1[n] != dd1)
      ans = (ans + d2[n << 1]) % P;
    else
      ans = (ans + min(d2[n], d2[n << 1])) % P;
    cout << ans << '\n';
    return;
  }
  getd2();
  ans = (1 << d1[n]) + d2[n] - 1;
  work();
  cout << ans << '\n';
}
int main() {
  int T;
  T = 1;
  while (T--) solve();
  return 0;
}
