#include <bits/stdc++.h>
using namespace std;
struct cmp {
  bool operator()(const pair<int, pair<int, int>>& a,
                  const pair<int, pair<int, int>>& b) {
    return a.second > b.second;
  }
};
pair<int, int> operator+(const pair<int, int>& a, const pair<int, int>& b) {
  return pair<int, int>(a.first + b.first, a.second + b.second);
}
long long binpow(long long b, long long e, long long mod) {
  long long ans = 1;
  while (e) {
    if (e & 1) ans = b * ans % mod;
    b = b * b % mod;
    e >>= 1;
  }
  return ans;
}
const int MAXN = 2e5 + 5;
const long long INF = 1e18;
const long long mod = 998244353;
int n, m, logm;
vector<int> adj[MAXN];
vector<pair<long long, long long>> adj2[20 * MAXN];
vector<pair<int, pair<int, int>>> adj3[2 * MAXN];
void dijkstra(int u, vector<long long>& dist) {
  vector<bool> vis(n * logm, false);
  dist.assign(n * logm, INF);
  priority_queue<pair<long long, long long>, vector<pair<long long, long long>>,
                 greater<pair<long long, long long>>>
      Q;
  Q.push({0, u});
  dist[u] = 0;
  while (!Q.empty()) {
    u = Q.top().second;
    Q.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for (auto e : adj2[u]) {
      if (dist[e.first] > dist[u] + e.second) {
        dist[e.first] = dist[u] + e.second;
        Q.push({dist[e.first], e.first});
      }
    }
  }
}
void dijkstra(int u, vector<pair<int, int>>& dist) {
  vector<bool> vis(2 * n, false);
  dist.assign(2 * n, make_pair((int)1e9, (int)1e9));
  priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>,
                 cmp>
      Q;
  Q.push(make_pair(u, pair<int, int>(0, 0)));
  dist[u] = {0, 0};
  while (!Q.empty()) {
    u = Q.top().first;
    Q.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for (auto e : adj3[u]) {
      if (dist[e.first] > dist[u] + e.second) {
        dist[e.first] = dist[u] + e.second;
        Q.push(make_pair(e.first, dist[e.first]));
      }
    }
  }
}
long long get_dist(pair<int, int>& a) {
  return (binpow(2, a.first, mod) - 1 + a.second) % mod;
}
long long solve() {
  for (int u = 0; u < n; u++) {
    adj3[u].push_back(make_pair(n + u, make_pair(1, 0)));
    adj3[n + u].push_back(make_pair(u, make_pair(1, 0)));
    for (auto v : adj[u]) {
      adj3[u].push_back(make_pair(v, make_pair(0, 1)));
      adj3[n + v].push_back(make_pair(n + u, make_pair(0, 1)));
    }
  }
  vector<pair<int, int>> dist;
  dijkstra(0, dist);
  if (dist[n - 1] < dist[2 * n - 1]) return get_dist(dist[n - 1]);
  return get_dist(dist[2 * n - 1]);
}
int main() {
  ;
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n >> m;
  logm = ceil(log2(m + 1));
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    adj[u].push_back(v);
  }
  for (int k = 0; k < logm; k++) {
    for (int u = 0; u < n; u++) {
      if (k) adj2[(k - 1) * n + u].push_back({k * n + u, 1 << (k - 1)});
      for (auto v : adj[u]) {
        if (k & 1)
          adj2[k * n + v].push_back({k * n + u, 1});
        else
          adj2[k * n + u].push_back({k * n + v, 1});
      }
    }
  }
  vector<long long> dist;
  dijkstra(0, dist);
  long long d = INF;
  for (int k = 0; k < logm; k++) d = min(d, dist[k * n + n - 1]);
  if (d >= INF) d = solve();
  cout << d << '\n';
  return 0;
}
