#include <bits/stdc++.h>
using namespace std;
const long long N = 5e5 + 5;
const long long mod = 998244353;
const long long INF = 0x7f7f7f7f7f7f7f7f;
const int INFi = 0x7f7f7f7f;
long long n, m, p2[N];
vector<pair<long long, long long>> adj[N];
vector<long long> dijkstra(int second) {
  vector<long long> d(n + 1, INF);
  d[second] = 0;
  set<pair<long long, long long>> q;
  q.insert({0, second});
  long long ct = 0;
  while (!q.empty()) {
    int v = q.begin()->second;
    q.erase(q.begin());
    for (auto i : adj[v]) {
      long long to = i.first;
      long long len = i.second ^ (d[v] & 1);
      if (d[v] + len < d[to]) {
        q.erase({d[to], to});
        d[to] = d[v] + len;
        q.insert({d[to], to});
      }
    }
  }
  return d;
}
void dijkstra1(int second, vector<long long> no) {
  vector<vector<long long>> d(n + 1, vector<long long>(30, INF));
  d[second][0] = 0;
  set<pair<long long, pair<long long, long long>>> q;
  q.insert({0, {second, 0}});
  long long ct = 0;
  while (!q.empty()) {
    pair<long long, long long> v = q.begin()->second;
    q.erase(q.begin());
    for (auto i : adj[v.first]) {
      long long to = i.first;
      long long len = 1;
      long long first = v.second + (i.second ^ ((v.second + no[v.first]) & 1)) +
                        no[v.first] - no[to];
      if (first > 29 || first < 0) continue;
      if (d[v.first][v.second] + 1 < d[to][first]) {
        q.erase({d[to][first], {to, first}});
        d[to][first] = d[v.first][v.second] + 1;
        q.insert({d[to][first], {to, first}});
      }
    }
  }
  long long mn = 0;
  for (int i = 1; i < 25; i++) {
    if ((no[n] + i) > 29) break;
    long long res = (1ll << (no[n] + i)) + d[n][i] - 1;
    long long resmn = (1ll << (no[n] + mn)) + d[n][mn] - 1;
    if (res < resmn) mn = i;
  }
  long long ans = p2[no[n] + mn] + d[n][mn] - 1;
  cout << ans << "\n";
}
void solve() {
  p2[0] = 1;
  for (int i = 1; i < N; i++) p2[i] = p2[i - 1] * 2 % mod;
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    long long u, v;
    cin >> u >> v;
    adj[u].push_back({v, 0});
    adj[v].push_back({u, 1});
  }
  vector<long long> d = dijkstra(1);
  dijkstra1(1, d);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << fixed;
  cout << setprecision(15);
  ;
  int test = 1;
  for (int i = 1; i <= test; i++) {
    solve();
  }
}
