#include <bits/stdc++.h>
using namespace std;
int read() {
  int w = 0, f = 1;
  char c = ' ';
  while (c < '0' || c > '9') c = getchar(), f = c == '-' ? -1 : f;
  while (c >= '0' && c <= '9') w = w * 10 + c - 48, c = getchar();
  return w * f;
}
struct node {
  int u, d;
  bool operator<(const node& o) const { return d > o.d; }
  node(int U, int D) { u = U, d = D; }
};
struct nodell {
  int u;
  long long d;
  bool operator<(const nodell& o) const { return d > o.d; }
  nodell(int U, long long D) { u = U, d = D; }
};
const int inf = 1e8, mod = 998244353;
const long long infll = 1e16;
int n, m, dis[200005 * 20];
long long minn[200005 << 1];
bool vis[200005 * 20];
vector<pair<int, int> > e[200005 * 20], e1[200005 << 1];
void dij1() {
  priority_queue<nodell> q;
  for (int i = 0; i < n * 2; i++) minn[i] = infll;
  q.push(nodell(n - 1, 0));
  q.push(nodell(n * 2 - 1, 0));
  minn[n - 1] = minn[n * 2 - 1] = 0;
  while (!q.empty()) {
    int u = q.top().u;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto i : e1[u]) {
      int v = i.first;
      long long w = i.second;
      if (minn[v] > minn[u] + w) {
        minn[v] = minn[u] + w;
        if (!vis[v]) q.push(nodell(v, minn[v]));
      }
    }
  }
}
void dij2() {
  int s = 0;
  priority_queue<node> q;
  for (int i = 0; i < n * 20; i++) dis[i] = inf, vis[i] = 0;
  q.push(node(s, 0));
  dis[s] = 0;
  while (!q.empty()) {
    int u = q.top().u;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto i : e[u]) {
      int v = i.first, w = i.second;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        if (!vis[v]) q.push(node(v, dis[v]));
      }
    }
  }
}
signed main() {
  n = read(), m = read();
  for (int i = 1; i <= m; i++) {
    int x = read(), y = read();
    for (int j = 0; j < 20; j++)
      if (j & 1)
        e[j * n + y - 1].push_back(make_pair(j * n + x - 1, 1));
      else
        e[j * n + x - 1].push_back(make_pair(j * n + y - 1, 1));
    e1[x - 1].push_back(make_pair(y - 1, 1));
    e1[n + y - 1].push_back(make_pair(n + x - 1, 1));
  }
  for (int i = 0; i < 19; i++)
    for (int j = 1; j <= n; j++)
      e[i * n + j - 1].push_back(make_pair((i + 1) * n + j - 1, 1 << i));
  for (int i = 1; i <= n; i++)
    e1[i - 1].push_back(make_pair(n + i - 1, 1 << 20)),
        e1[n + i - 1].push_back(make_pair(i - 1, 1 << 20));
  dij1();
  dij2();
  int ans = inf;
  for (int i = 0; i < 20; i++) ans = min(ans, dis[i * n + n - 1]);
  if (ans != inf) return printf("%d\n", ans), 0;
  long long minc = infll;
  for (int i = 1; i <= n; i++)
    if (dis[19 * n + i - 1] != inf) {
      if (minn[i - 1] < minc)
        minc = minn[i - 1],
        ans = dis[19 * n + i - 1] + (minc & ((1 << 20) - 1));
      if (minn[i - 1] == minc)
        ans = min(ans, dis[19 * n + i - 1] + (int)(minc & ((1 << 20) - 1)));
    }
  for (int i = 19, j = 1 << 19; i <= 19 + (minc >> 20) - 1;
       i++, j = (j << 1) % mod)
    ans = (ans + j) % mod;
  printf("%d\n", ans);
  return 0;
}
