#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
template <class T1, class T2>
struct cmpf {
  bool rev;
  inline bool operator()(const pair<T1, T2>& a, const pair<T1, T2>& b) const {
    return (a.first < b.first) ^ rev;
  }
  cmpf(bool b = false) { rev = b; }
};
template <class T1, class T2>
struct cmps {
  bool rev;
  inline bool operator()(const pair<T1, T2>& a, const pair<T1, T2>& b) const {
    return (a.second < b.second) ^ rev;
  }
  cmps(bool b = false) { rev = b; }
};
long long binpow(long long x, long long p, const long long& mod) {
  assert(mod > 0);
  long long ret = 1;
  for (; p > 0; p >>= 1, x = x * x % mod)
    if (p & 1) ret = ret * x % mod;
  return ret;
}
template <class T>
bool chmn(T& a, const T& b) {
  return (greater<T>()(a, b) ? (a = b, true) : false);
}
template <class T>
bool chmx(T& a, const T& b) {
  return (less<T>()(a, b) ? (a = b, true) : false);
}
void setIO(const string& filename = "") {
  if (filename.size() > 0) {
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
  }
  cin.tie(0)->sync_with_stdio(0);
}
int chr[8] = {-1, 0, 1, 0, -1, -1, 1, 1};
int chc[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const long long MOD = 998244353;
const int INIT = 1001001001;
const int MN = 201001;
const int LG = 20;
const long long INF = 2e18 + 1;
long long N, M, K, Q;
long long A[MN];
set<long long> adj[MN], radj[MN];
struct Item {
  long long node;
  long long dst, revs;
  Item(const long long _node, const long long _dst, const long long _revs) {
    node = _node;
    dst = _dst;
    revs = _revs;
  }
  inline const bool operator<(const Item& o) const {
    if (revs == o.revs) {
      if (dst == o.dst) return node > o.node;
      return dst > o.dst;
    }
    return revs > o.revs;
  }
  void print() const {
    cerr << "Item node,revs,dst: " << node << ' ' << revs << ' ' << dst << endl;
  }
};
long long dist[LG + 1][MN];
long long p2[MN];
pair<long long, long long> V[2][MN];
void solve(int testcase) {
  cin >> N >> M;
  for (int i = 0; i < M; ++i) {
    long long u, v;
    cin >> u >> v;
    --u;
    --v;
    adj[u].insert(v);
    radj[v].insert(u);
  }
  p2[0] = 1;
  for (int i = 1; i < MN; ++i) {
    p2[i] = p2[i - 1] << 1;
    if (i >= 56) {
      p2[i] %= MOD;
    }
  }
  priority_queue<pair<long long, long long>, vector<pair<long long, long long>>,
                 greater<pair<long long, long long>>>
      pq[LG + 1];
  pq[0].emplace(0, 0);
  for (int i = 0; i <= LG; ++i) fill(dist[i], dist[i] + N, INF);
  dist[0][0] = 0;
  long long ans = INF;
  for (int i = 0; i < LG; ++i) {
    while (pq[i].size() > 0) {
      const pair<long long, long long> cur = pq[i].top();
      pq[i].pop();
      (i, cur);
      if (cur.second == N - 1) {
        chmn(ans, cur.first);
        continue;
      }
      if (i & 1) {
        for (const long long v : radj[cur.second]) {
          if (chmn(dist[i][v], cur.first + 1)) {
            pq[i].emplace(dist[i][v], v);
          }
        }
      } else {
        for (const long long v : adj[cur.second]) {
          if (chmn(dist[i][v], cur.first + 1)) {
            pq[i].emplace(dist[i][v], v);
          }
        }
      }
      if (chmn(dist[i + 1][cur.second], cur.first + p2[i])) {
        pq[i + 1].emplace(dist[i + 1][cur.second], cur.second);
      }
    }
  }
  if (ans != INF) {
    cout << ans % MOD << endl;
    return;
  }
  fill(V[0], V[0] + N, pair<long long, long long>(INF, INF));
  fill(V[1], V[1] + N, pair<long long, long long>(INF, INF));
  priority_queue<Item> pq2;
  while (pq[LG].size() > 0) {
    const pair<long long, long long> cur = pq[LG].top();
    pq[LG].pop();
    if (V[LG & 1][cur.second].first == LG) continue;
    const long long D = cur.first - (p2[LG] - 1);
    if (chmn(V[LG & 1][cur.second], pair<long long, long long>(LG, D))) {
      (D, cur.second);
      assert(0 <= D);
      assert(D < M);
      pq2.emplace(cur.second, D, LG);
    }
  }
  while (pq2.size() > 0) {
    const Item cur = pq2.top();
    pq2.pop();
    if (cur.node == N - 1) {
      cout << (cur.dst + p2[cur.revs] - 1) % MOD << endl;
      return;
    }
    for (const long long v : adj[cur.node]) {
      const bool flip = cur.revs & 1;
      const long long new_revs = cur.revs + flip;
      if (chmn(V[new_revs & 1][v],
               pair<long long, long long>(new_revs, cur.dst + 1))) {
        pq2.emplace(v, cur.dst + 1, new_revs);
      }
    }
    for (const long long v : radj[cur.node]) {
      const bool flip = !(cur.revs & 1);
      const long long new_revs = cur.revs + flip;
      if (chmn(V[new_revs & 1][v],
               pair<long long, long long>(new_revs, cur.dst + 1))) {
        pq2.emplace(v, cur.dst + 1, new_revs);
      }
    }
  }
  assert(false);
}
int main() {
  setIO();
  long long T = 1;
  for (int t = 1; t <= T; ++t) {
    solve(t);
  }
  return 0;
}
