#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <class T>
void IN(T& x) {
  cin >> x;
}
template <class H, class... T>
void IN(H& h, T&... t) {
  IN(h);
  IN(t...);
}
template <class T1, class T2>
void OUT(const pair<T1, T2>& x);
template <class T>
void OUT(const vector<T>& x);
template <class T>
void OUT(const T& x) {
  cout << x;
}
template <class H, class... T>
void OUT(const H& h, const T&... t) {
  OUT(h);
  OUT(t...);
}
template <class T1, class T2>
void OUT(const pair<T1, T2>& x) {
  OUT(x.first, ' ', x.second);
}
template <class T>
void OUT(const vector<T>& x) {
  for (int i = int(0); i < int(x.size()); i++) OUT(i == 0 ? "" : " ", x[i]);
}
template <class... T>
void OUTL(const T&... t) {
  OUT(t..., "\n");
}
template <class H>
void OUTLS(const H& h) {
  OUTL(h);
}
template <class H, class... T>
void OUTLS(const H& h, const T&... t) {
  OUT(h, ' ');
  OUTLS(t...);
}
long long MOD = 998244353;
inline long long mod(long long x_) { return (x_) % MOD; }
long long modpow(long long x_, long long N_) {
  if (N_ == 0) return 1;
  long long a = modpow(x_, N_ / 2);
  a = (a * a) % MOD;
  if (N_ % 2) a = (a * x_) % MOD;
  return a;
}
long long inv(long long x_) { return modpow(x_, MOD - 2); }
class mi {
 public:
  mi(long long v = 0) { value = v; }
  mi operator+(long long rs) { return mod(value + rs); }
  mi operator-(long long rs) { return mod(value - rs + MOD); }
  mi operator*(long long rs) { return mod(value * rs); }
  mi operator/(long long rs) { return mod(value * inv(rs)); }
  mi& operator+=(long long rs) {
    *this = (*this) + rs;
    return *this;
  }
  mi& operator-=(long long rs) {
    *this = (*this) - rs;
    return *this;
  }
  mi& operator*=(long long rs) {
    *this = (*this) * rs;
    return *this;
  }
  mi& operator/=(long long rs) {
    *this = (*this) / rs;
    return *this;
  }
  operator long long&() { return value; }
  long long value;
};
void program();
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  program();
}
const int MX = 1e6;
const int K = 20;
int n, m;
vector<pair<int, int>> adj[MX];
pair<int, int> dist[MX];
int DIST[MX][K];
void program() {
  IN(n, m);
  for (int i = int(0); i < int(m); i++) {
    int u, v;
    IN(u, v);
    adj[u].push_back({v, 0});
    adj[v + n].push_back({u + n, 0});
  }
  for (int i = int(1); i < int(n + 1); i++) adj[i].push_back({i + n, 1});
  for (int i = int(1); i < int(n + 1); i++) adj[i + n].push_back({i, 1});
  priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>,
                 greater<tuple<int, int, int>>>
      pq;
  for (int i = int(1); i < int(n * 2 + 1); i++) dist[i] = {1e9, 1e9};
  pq.push({0, 0, 1});
  dist[1] = {0, 0};
  while (!pq.empty()) {
    int d1, d2, u;
    tie(d1, d2, u) = pq.top();
    pq.pop();
    if (dist[u] != pair<int, int>(d1, d2)) continue;
    for (auto& v : adj[u]) {
      pair<int, int> nd = {v.second + d1, 1 - v.second + d2};
      if (nd < dist[v.first]) {
        dist[v.first] = nd;
        pq.push({nd.first, nd.second, v.first});
      }
    }
  }
  pair<int, int> pAns = min(dist[n * 2], dist[n]);
  mi ans = modpow(2, pAns.first) - 1 + pAns.second;
  if (pAns.first <= K) {
    for (int i = int(1); i < int(n * 2 + 1); i++)
      for (int j = int(0); j < int(K); j++) DIST[i][j] = 1e9;
    pq.push({0, 1, 0});
    DIST[1][0] = 0;
    while (!pq.empty()) {
      int d, u, k;
      tie(d, u, k) = pq.top();
      pq.pop();
      if (DIST[u][k] != d) continue;
      for (auto& v : adj[u]) {
        int nk = v.second + k;
        int nd = d + 1 - v.second;
        if (v.second) nd += (1 << k);
        if (nk >= K) continue;
        if (nd < DIST[v.first][nk]) {
          DIST[v.first][nk] = nd;
          pq.push({nd, v.first, nk});
        }
      }
    }
    for (int j = int(0); j < int(K); j++)
      ans = min(int(ans), min(DIST[n][j], DIST[n * 2][j]));
  }
  OUTL((long long)ans);
}
