#include <bits/stdc++.h>
template <typename T1, typename T2>
inline bool chkmin(T1& x, const T2& y) {
  if (x > y) {
    x = y;
    return 1;
  }
  return 0;
}
template <typename T1, typename T2>
inline bool chkmax(T1& x, const T2& y) {
  if (x < y) {
    x = y;
    return 1;
  }
  return 0;
}
using namespace std;
const long long maxn = 2e5 + 20;
ostream& operator<<(ostream& out, vector<long long>& v) {
  for (auto& x : v) out << x << ' ';
  return out;
}
ostream& operator<<(ostream& out, pair<long long, long long>& v) {
  out << v.first << ", " << v.second;
  return out;
}
istream& operator>>(istream& in, pair<long long, long long>& a) {
  in >> a.first >> a.second;
  return in;
}
const long long inf = (long long)2e9;
const long double pi = asin(1) * 2;
const long double eps = 1e-8;
const long long mod = 998244353;
const long long ns = 97;
const long long LOG = 18;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
vector<pair<long long, long long>> g[maxn * LOG];
vector<pair<long long, pair<long long, long long>>> gr[maxn * 2];
long long d[maxn * LOG], n;
pair<long long, long long> dist[maxn * 2];
long long Dijkstra() {
  for (auto& x : d) x = inf;
  d[0] = 0;
  set<pair<long long, long long>> a;
  a.insert({0, 0});
  while (!a.empty()) {
    long long v = a.begin()->second;
    ;
    a.erase(a.begin());
    for (auto& u : g[v]) {
      long long to = u.first, c = u.second;
      if (d[to] > d[v] + c) {
        a.erase({d[to], to});
        d[to] = d[v] + c;
        a.insert({d[to], to});
      }
    }
  }
  long long res = inf;
  for (long long i = 0; i < LOG; ++i) chkmin(res, d[n - 1 + n * i]);
  ;
  return res;
}
long long mult(long long a, long long b) { return a * b % mod; }
long long add(long long a, long long b) {
  long long c = a + b;
  if (c >= mod) c -= mod;
  return c;
}
long long powmod(long long a, long long n) {
  if (n == 0) return 1;
  if (n % 2) return mult(a, powmod(a, n - 1));
  long long b = powmod(a, n / 2);
  return mult(b, b);
}
long long inv(long long a) { return powmod(a, mod - 2); }
long long Dij() {
  for (auto& x : dist) x = {inf, inf};
  dist[0] = {0, 0};
  set<pair<pair<long long, long long>, long long>> a;
  a.insert({{0, 0}, 0});
  while (!a.empty()) {
    long long v = a.begin()->second;
    a.erase(a.begin());
    for (auto& u : gr[v]) {
      auto x = u.second;
      auto now = dist[v];
      now.first += x.first, now.second += x.second;
      if (dist[u.first] > now) {
        a.erase({dist[u.first], u.first});
        dist[u.first] = now;
        a.insert({dist[u.first], u.first});
      }
    }
  }
  pair<long long, long long> res = {inf, inf};
  chkmin(res, dist[n - 1]);
  chkmin(res, dist[n - 1 + n]);
  long long ans = 0;
  for (long long i = 0; i < res.first; ++i) {
    ans = add(ans, powmod(2, i));
  }
  ans = add(ans, res.second);
  return ans;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  long long m;
  cin >> n >> m;
  for (long long i = 0; i < m; ++i) {
    long long a, b;
    cin >> a >> b;
    --a, --b;
    for (long long j = 0; j < LOG; ++j) {
      if (j & 1)
        g[b + n * j].push_back({a + n * j, 1});
      else
        g[a + n * j].push_back({b + n * j, 1});
    }
    gr[a].push_back({b, {0, 1}});
    gr[b + n].push_back({a + n, {0, 1}});
  }
  for (long long i = 0; i < n; ++i) {
    for (long long j = 0; j < LOG - 1; ++j) {
      g[i + n * j].push_back({i + n * j + n, (1 << j)});
    }
    gr[i].push_back({i + n, {1, 0}});
    gr[i + n].push_back({i, {1, 0}});
  }
  auto res = Dijkstra();
  if (res != inf) {
    cout << res << '\n';
    exit(0);
  }
  cout << Dij() << '\n';
}
