#include <bits/stdc++.h>
using namespace std;
const long long MOD = (long long)998244353;
const int SIZE = 2e5 + 5;
const long long INF = 1LL << 36;
const double eps = 1e-4;
const double PI = 3.1415926535897932;
pair<int, int> dist1[400009];
vector<int> adj[400009];
priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>,
               greater<pair<pair<int, int>, int>>>
    pq1;
long long dist2[400009][30];
priority_queue<pair<long long, pair<int, int>>,
               vector<pair<long long, pair<int, int>>>,
               greater<pair<long long, pair<int, int>>>>
    pq2;
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < (m); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    adj[a].push_back(b);
    adj[b + n].push_back(a + n);
  }
  for (int i = 0; i < (2 * n); ++i) dist1[i] = make_pair(1e9, 1e9);
  dist1[0] = make_pair(0, 0);
  pq1.push({{0, 0}, 0});
  while (((int)(pq1).size())) {
    auto f = pq1.top();
    pq1.pop();
    int x = f.second;
    if (dist1[x] < f.first) continue;
    for (int i : adj[x]) {
      pair<int, int> nd = dist1[x];
      nd.second++;
      if (nd < dist1[i]) {
        dist1[i] = nd;
        pq1.push({dist1[i], i});
      }
    }
    int i = x;
    if (x >= n)
      i -= n;
    else
      i += n;
    pair<int, int> nd = dist1[x];
    nd.first++;
    if (nd < dist1[i]) {
      dist1[i] = nd;
      pq1.push({dist1[i], i});
    }
  }
  pair<int, int> ans1 = min(dist1[n - 1], dist1[2 * n - 1]);
  for (int i = 0; i < (2 * n); ++i)
    for (int j = 0; j < (30); ++j) dist2[i][j] = INF;
  dist2[0][0] = 0;
  pq2.push({0, {0, 0}});
  long long ans2 = INF;
  while (((int)(pq2).size())) {
    auto fr = pq2.top();
    pq2.pop();
    int x = fr.second.first, f = fr.second.second;
    if (dist2[x][f] < fr.first) continue;
    if (x % n == n - 1) {
      ans2 = fr.first;
      break;
    }
    for (int i : adj[x]) {
      long long nd = dist2[x][f] + 1;
      if (nd < dist2[i][f]) {
        dist2[i][f] = nd;
        pq2.push({dist2[i][f], {i, f}});
      }
    }
    if (f >= 29) continue;
    int i = x;
    if (x >= n)
      i -= n;
    else
      i += n;
    long long nd = dist2[x][f] + (1LL << f);
    if (nd < dist2[i][f + 1]) {
      dist2[i][f + 1] = nd;
      pq2.push({dist2[i][f + 1], {i, f + 1}});
    }
  }
  if (ans2 == INF) {
    long long ans = ans1.second;
    long long p2 = 1;
    for (int j = 0; j < (ans1.first); ++j) p2 = (p2 * 2) % MOD;
    cout << (ans + p2 + MOD - 1) % MOD;
    return 0;
  } else {
    if (ans1.first < 40) {
      long long ans = ans1.second;
      long long p2 = 1;
      for (int j = 0; j < (ans1.first); ++j) p2 = (p2 * 2) % MOD;
      ans2 = min(ans2, ans + p2 + MOD - 1);
    }
    cout << ans2 % MOD;
  }
}
