#include <bits/stdc++.h>
using namespace std;
template <class T = int>
T read() {
  T x = 0;
  char ch = 0;
  bool f = false;
  while (!isdigit(ch)) f |= (ch = getchar()) == '-';
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ '0');
  return f ? -x : x;
}
const int MOD = 998244353;
pair<int, int> operator+(pair<int, int> a, pair<int, int> b) {
  return {a.first + b.first, a.second + b.second};
}
int mv(pair<int, int> p) {
  int ans = p.second;
  int w = 1;
  for (int _ = 0; _ < (int)(p.first); _++) {
    ans = (ans + w) % MOD;
    w = (w << 1) % MOD;
  }
  return ans;
}
const int N = 200200;
struct E {
  int v;
  pair<int, int> w;
};
const int L = 20;
const int NS = N * (L + 2);
vector<E> es[NS];
void ae(int u, int v, pair<int, int> w) { es[u].push_back({v, w}); }
int u[N], v[N];
int n = read(), m = read();
int id(int x, int l) { return x + l * n; }
pair<int, int> dis[NS];
bool vis[NS];
int main() {
  for (int i = (int)(1); i <= (int)(m); i++) {
    u[i] = read();
    v[i] = read();
  }
  for (int i = (int)(0); i <= (int)(L + 1); i++) {
    if (i & 1)
      for (int j = (int)(1); j <= (int)(m); j++)
        ae(id(v[j], i), id(u[j], i), {0, 1});
    else
      for (int j = (int)(1); j <= (int)(m); j++)
        ae(id(u[j], i), id(v[j], i), {0, 1});
  }
  for (int i = (int)(0); i <= (int)(L + 1); i++) {
    if (i == L + 1)
      for (int j = (int)(1); j <= (int)(n); j++)
        ae(id(j, i), id(j, i - 1), {1, 0});
    else
      for (int j = (int)(1); j <= (int)(n); j++)
        ae(id(j, i), id(j, i + 1), {1, 0});
  }
  priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>,
                 greater<pair<pair<int, int>, int>>>
      pq;
  dis[id(1, 0)] = {0, 0};
  pq.push({{0, 0}, 1});
  vis[id(1, 0)] = true;
  while (!pq.empty()) {
    pair<pair<int, int>, int> p = pq.top();
    pq.pop();
    int x = p.second;
    pair<int, int> dx = p.first;
    if (dx != dis[x]) continue;
    for (E e : es[x]) {
      pair<int, int> td = dx + e.w;
      if (!vis[e.v] || td < dis[e.v]) {
        dis[e.v] = td;
        pq.push({td, e.v});
        vis[e.v] = true;
      }
    }
  }
  bool ol = false;
  for (int i = 0; i < (int)(L); i++)
    if (vis[id(n, i)]) ol = true;
  int ans = MOD - 1;
  if (ol) {
    for (int i = 0; i < (int)(L); i++)
      if (vis[id(n, i)]) ans = min(ans, mv(dis[id(n, i)]));
  } else {
    pair<int, int> pp{1e9, 1e9};
    for (int i = (int)(L); i <= (int)(L + 1); i++)
      if (vis[id(n, i)]) pp = min(pp, dis[id(n, i)]);
    ans = mv(pp);
  }
  printf("%d\n", ans);
  return 0;
}
