#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T, class U>
void chmin(T& t, const U& u) {
  if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
  if (t < u) t = u;
}
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{";
  for (int i = 0; i < (v.size()); i++) {
    if (i) os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}
template <unsigned int MOD>
struct ModInt {
  using uint = unsigned int;
  using ull = unsigned long long;
  using M = ModInt;
  uint v;
  ModInt(ll _v = 0) { set_norm(_v % MOD + MOD); }
  M& set_norm(uint _v) {
    v = (_v < MOD) ? _v : _v - MOD;
    return *this;
  }
  explicit operator bool() const { return v != 0; }
  explicit operator int() const { return v; }
  M operator+(const M& a) const { return M().set_norm(v + a.v); }
  M operator-(const M& a) const { return M().set_norm(v + MOD - a.v); }
  M operator*(const M& a) const { return M().set_norm(ull(v) * a.v % MOD); }
  M operator/(const M& a) const { return *this * a.inv(); }
  M& operator+=(const M& a) { return *this = *this + a; }
  M& operator-=(const M& a) { return *this = *this - a; }
  M& operator*=(const M& a) { return *this = *this * a; }
  M& operator/=(const M& a) { return *this = *this / a; }
  M operator-() const { return M() - *this; }
  M& operator++(int) { return *this = *this + 1; }
  M& operator--(int) { return *this = *this - 1; }
  M pow(ll n) const {
    if (n < 0) return inv().pow(-n);
    M x = *this, res = 1;
    while (n) {
      if (n & 1) res *= x;
      x *= x;
      n >>= 1;
    }
    return res;
  }
  M inv() const {
    ll a = v, b = MOD, p = 1, q = 0, t;
    while (b != 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(p -= t * q, q);
    }
    return M(p);
  }
  bool operator==(const M& a) const { return v == a.v; }
  bool operator!=(const M& a) const { return v != a.v; }
  friend ostream& operator<<(ostream& os, const M& a) { return os << a.v; }
  friend istream& operator>>(istream& in, M& x) {
    ll v_;
    in >> v_;
    x = M(v_);
    return in;
  }
  static uint get_mod() { return MOD; }
};
using Mint = ModInt<998244353>;
const ll INF = TEN(18);
const int maxn = 200010;
ll d[maxn][20];
pair<int, int> dx[maxn][2];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  VV<int> g(n), rg(n);
  for (int i = 0; i < (m); i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].push_back(b);
    rg[b].push_back(a);
  }
  {
    for (int i = 0; i < (n); i++)
      for (int j = 0; j < (20); j++) d[i][j] = INF;
    d[0][0] = 0;
    using Data = pair<ll, pii>;
    priority_queue<Data, V<Data>, greater<Data>> que;
    que.emplace(0, make_pair(0, 0));
    while (!que.empty()) {
      auto t = que.top();
      que.pop();
      int v, k;
      tie(v, k) = t.second;
      if (d[v][k] < t.first) continue;
      if (k < 19) {
        ll nd = d[v][k] + (1ll << k);
        if (nd < d[v][k + 1]) {
          d[v][k + 1] = nd;
          que.emplace(nd, make_pair(v, k + 1));
        }
      }
      for (auto to : (k % 2 == 0 ? g[v] : rg[v])) {
        ll nd = d[v][k] + 1;
        if (nd < d[to][k]) {
          d[to][k] = nd;
          que.emplace(nd, make_pair(to, k));
        }
      }
    }
    ll ans = INF;
    for (int i = 0; i < (20); i++) {
      if (d[n - 1][i] != INF) {
        chmin(ans, d[n - 1][i]);
      }
    }
    if (ans != INF) {
      cout << Mint(ans) << endl;
      return 0;
    }
  }
  for (int i = 0; i < (n); i++)
    for (int j = 0; j < (2); j++) dx[i][j] = make_pair(1e9, 1e9);
  using Data = pair<pii, pii>;
  priority_queue<Data, V<Data>, greater<Data>> que;
  dx[0][0] = make_pair(0, 0);
  que.emplace(make_pair(0, 0), make_pair(0, 0));
  while (!que.empty()) {
    auto t = que.top();
    que.pop();
    int v, k;
    tie(v, k) = t.second;
    if (dx[v][k] < t.first) continue;
    int rev, es;
    tie(rev, es) = t.first;
    {
      if (make_pair(rev + 1, es) < dx[v][k ^ 1]) {
        dx[v][k ^ 1] = make_pair(rev + 1, es);
        que.emplace(make_pair(rev + 1, es), make_pair(v, k ^ 1));
      }
    }
    for (auto to : (k == 0 ? g[v] : rg[v])) {
      if (make_pair(rev, es + 1) < dx[to][k]) {
        dx[to][k] = make_pair(rev, es + 1);
        que.emplace(make_pair(rev, es + 1), make_pair(to, k));
      }
    }
  }
  auto p = min(dx[n - 1][0], dx[n - 1][1]);
  cout << Mint(2).pow(p.first) - 1 + p.second << endl;
  return 0;
}
