#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, M = 10000000;
const long long INF = 1e18 + 5;
inline long long read() {
  long long sum = 0, fh = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') fh = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    sum = sum * 10 + c - '0';
    c = getchar();
  }
  return sum * fh;
}
inline int read2() {
  char c = getchar();
  while (c < '0' || c > '9') {
    c = getchar();
  }
  return c - '0';
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
inline long long ab(long long x) { return x < 0 ? -x : x; }
struct miaow {
  int f, t, c, l;
  miaow(int f = 0, int t = 0, int c = 0, int l = 0) : f(f), t(t), c(c), l(l) {}
} imap[M + 5];
int str[M + 5] = {0}, cou = 1;
inline void jb(int f, int t, int c) {
  imap[cou] = miaow(f, t, c, str[f]);
  str[f] = cou++;
}
const long long p = 998244353;
pair<int, int> bj[N];
int n, m;
long long dj = 1, djcs = 0;
inline void csh() {
  ++djcs;
  for (int i = 1; i <= n; ++i) {
    int f = i + (djcs - 1) * n, t = i + djcs * n;
    jb(f, t, dj);
  }
  for (int i = 1; i <= m; ++i) {
    int f = bj[i].first + djcs * n, t = bj[i].second + djcs * n;
    if (djcs & 1) {
      jb(t, f, 1);
    } else
      jb(f, t, 1);
  }
  while (dj <= n) {
    dj *= 2;
    ++djcs;
    for (int i = 1; i <= n; ++i) {
      int f = i + (djcs - 1) * n, t = i + djcs * n;
      jb(f, t, dj);
    }
    for (int i = 1; i <= m; ++i) {
      int f = bj[i].first + djcs * n, t = bj[i].second + djcs * n;
      if (djcs & 1) {
        jb(t, f, 1);
      } else
        jb(f, t, 1);
    }
  }
}
int jl[M] = {0};
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>
    qwe;
inline void dijk() {
  jl[1] = 1;
  qwe.push(pair<int, int>(jl[1], 1));
  while (!qwe.empty()) {
    pair<int, int> asd = qwe.top();
    qwe.pop();
    int x = asd.first, y = asd.second;
    if (x > jl[y]) continue;
    for (int i = str[y]; i; i = imap[i].l) {
      int t = imap[i].t, c = imap[i].c;
      if (!jl[t]) {
        jl[t] = x + c;
        qwe.push(pair<int, int>(jl[t], t));
      } else if (jl[t] > x + c) {
        jl[t] = x + c;
        qwe.push(pair<int, int>(jl[t], t));
      }
    }
  }
}
miaow imap1[N], imap2[N];
int str1[N] = {0}, cou1 = 1, str2[N] = {0}, cou2 = 1;
inline void jb12(int f, int t, int c) {
  imap1[cou1] = miaow(f, t, c, str1[f]);
  str1[f] = cou1++;
  imap2[cou2] = miaow(t, f, c, str2[t]);
  str2[t] = cou2++;
}
int jl1[N] = {0}, jl2[N] = {0};
vector<int> dl1, dl2;
inline void csh2() {
  for (int i = 1; i <= m; ++i) {
    int f = bj[i].first, t = bj[i].second;
    jb12(f, t, 1);
  }
  for (int i = 1; i <= n; ++i) {
    jl2[i] = jl[i + djcs * n];
    if (jl2[i]) {
      dl1.push_back(i);
    }
  }
}
inline long long dijk2() {
  long long sum = 0, dddd = dj * 2;
  do {
    dj = dj * 2 % p;
    sum = (sum + dj) % p;
    ++djcs;
    sort(dl1.begin(), dl1.end());
    for (int i = 0; i < dl2.size(); ++i) {
      int x = dl2[i];
      qwe.push(pair<int, int>(jl2[x], x));
      jl1[x] = jl2[x];
    }
    dl2.clear();
    for (int i = 0; i < dl1.size(); ++i) {
      int x = dl1[i];
      qwe.push(pair<int, int>(jl2[x], x));
      dl2.push_back(x);
    }
    dl1.clear();
    if (djcs & 1) {
      while (!qwe.empty()) {
        pair<int, int> asd = qwe.top();
        qwe.pop();
        int x = asd.first, y = asd.second;
        if (x > jl2[y]) continue;
        for (int i = str2[y]; i; i = imap2[i].l) {
          int t = imap2[i].t, c = imap2[i].c;
          if (jl1[t]) continue;
          if (!jl2[t]) {
            dl1.push_back(t);
            jl2[t] = x + c;
            qwe.push(pair<int, int>(jl2[t], t));
          } else if (jl2[t] > x + c) {
            jl2[t] = x + c;
            qwe.push(pair<int, int>(jl2[t], t));
          }
        }
      }
    } else {
      while (!qwe.empty()) {
        pair<int, int> asd = qwe.top();
        qwe.pop();
        int x = asd.first, y = asd.second;
        if (x > jl2[y]) continue;
        for (int i = str1[y]; i; i = imap1[i].l) {
          int t = imap1[i].t, c = imap1[i].c;
          if (jl1[t]) continue;
          if (!jl2[t]) {
            dl1.push_back(t);
            jl2[t] = x + c;
            qwe.push(pair<int, int>(jl2[t], t));
          } else if (jl2[t] > x + c) {
            jl2[t] = x + c;
            qwe.push(pair<int, int>(jl2[t], t));
          }
        }
      }
    }
  } while (!jl2[n]);
  sort(dl1.begin(), dl1.end());
  for (int i = 0; i < dl1.size(); ++i) {
    int x = dl1[i];
    jl1[x] = jl2[x];
  }
  return (sum + jl2[n]) % p - 1 + p;
}
int main() {
  n = read(), m = read();
  for (int i = 1; i <= m; ++i) {
    int f = read(), t = read();
    bj[i] = pair<int, int>(f, t);
    jb(f, t, 1);
  }
  csh();
  dijk();
  int imi = 2147483647;
  for (int i = 0; i <= djcs; ++i) {
    if (jl[n + n * i]) imi = min(imi, jl[n + n * i]);
  }
  if (imi != 2147483647) {
    cout << imi - 1 << endl;
    return 0;
  }
  csh2();
  long long ans = dijk2() % p;
  cout << ans << endl;
}
