#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rnd64(
    chrono::high_resolution_clock::now().time_since_epoch().count());
long long power(long long a, long long m, long long mod) {
  long long ans = 1;
  while (m) {
    if (m % 2) ans *= a, ans %= (mod);
    a = (a * a) % mod;
    m >>= 1;
  }
  return ans;
}
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
  size_t operator()(pair<int64_t, int64_t> Y) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(Y.first * 31 + Y.second + FIXED_RANDOM);
  }
};
const long long inf = 1e18;
const long long M = 998244353;
vector<long long> adj[200001], adj2[200001];
void solve() {
  long long i, j, _;
  long long ans = inf;
  long long n, m, u, v;
  cin >> n >> m;
  while (m--) {
    cin >> u >> v;
    adj[u].push_back(v);
    adj2[v].push_back(u);
  }
  long long a[n + 1];
  for (i = 1; i < n + 1; i++) a[i] = inf;
  _ = 20;
  long long now = 0, k = 0;
  long long vis1[n + 1], v1[n + 1];
  a[1] = 0;
  while (_--) {
    set<pair<long long, long long> > st;
    for (i = 1; i < n + 1; i++) vis1[i] = 0, st.insert({a[i], i}), v1[i] = 1;
    if (now) {
      while (st.size()) {
        long long z = (*st.begin()).second;
        st.erase(st.begin());
        vis1[z] = 1;
        for (auto i : adj2[z]) {
          if (vis1[i]) continue;
          auto it = st.find({a[i], i});
          st.erase(it);
          if (a[i] > a[z] + 1 + k * v1[z]) {
            a[i] = a[z] + 1 + k * v1[z];
            v1[i] = 0;
          }
          st.insert({a[i], i});
        }
      }
    } else {
      while (st.size()) {
        long long z = (*st.begin()).second;
        st.erase(st.begin());
        vis1[z] = 1;
        for (auto i : adj[z]) {
          if (vis1[i]) continue;
          auto it = st.find({a[i], i});
          st.erase(it);
          if (a[i] > a[z] + 1 + k * v1[z]) {
            a[i] = a[z] + 1 + k * v1[z];
            v1[i] = 0;
          }
          st.insert({a[i], i});
        }
      }
    }
    now = !now;
    k *= 2;
    if (!k) ++k;
  }
  if (a[n] != inf) {
    cout << a[n] % M << '\n';
    return;
  }
  long long dp[n + 1][2];
  dp[1][0] = 0, dp[1][1] = 1;
  for (i = 2; i < n + 1; i++) dp[i][0] = inf, dp[i][1] = inf;
  set<pair<pair<long long, long long>, pair<long long, long long> > > st;
  long long vis[n + 1][2];
  long long pre[n + 1][2];
  for (i = 0; i < n + 1; i++)
    for (j = 0; j < 2; j++) vis[i][j] = 0, pre[i][j] = 0;
  for (i = 1; i < n + 1; i++) {
    for (j = 0; j < 2; j++) {
      st.insert({{dp[i][j], pre[i][j]}, {i, j}});
    }
  }
  while (st.size()) {
    pair<long long, long long> z = (*st.begin()).second;
    st.erase(st.begin());
    vis[z.first][z.second] = 1;
    long long p = 0;
    if (z.second) {
      ++p;
    }
    for (auto i : adj[z.first]) {
      if (vis[i][0]) continue;
      if ((dp[i][0] < dp[z.first][z.second] + p) ||
          (dp[i][0] == dp[z.first][z.second] + p &&
           pre[i][0] <= pre[z.first][z.second] + 1))
        continue;
      st.erase(st.find({{dp[i][0], pre[i][0]}, {i, 0}}));
      dp[i][0] = dp[z.first][z.second] + p;
      pre[i][0] = pre[z.first][z.second] + 1;
      st.insert({{dp[i][0], pre[i][0]}, {i, 0}});
    }
    p = 0;
    if (!z.second) {
      ++p;
    }
    for (auto i : adj2[z.first]) {
      if (vis[i][1]) continue;
      if ((dp[i][1] < dp[z.first][z.second] + p) ||
          (dp[i][1] == dp[z.first][z.second] + p &&
           pre[i][1] <= pre[z.first][z.second] + 1))
        continue;
      st.erase(st.find({{dp[i][1], pre[i][1]}, {i, 1}}));
      dp[i][1] = dp[z.first][z.second] + p;
      pre[i][1] = pre[z.first][z.second] + 1;
      st.insert({{dp[i][1], pre[i][1]}, {i, 1}});
    }
  }
  if (dp[n][1] == dp[n][0]) {
    cout << (power(2, dp[n][0], M) + min(pre[n][1], pre[n][0]) + M - 1) % M
         << '\n';
    return;
  }
  if (dp[n][1] < dp[n][0]) {
    cout << (power(2, dp[n][1], M) + pre[n][1] + M - 1) % M << '\n';
    return;
  }
  cout << (power(2, dp[n][0], M) + pre[n][0] + M - 1) % M << '\n';
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long T = 1;
  while (T--) {
    solve();
  }
  return 0;
}
