#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<int, int>> G[262144];
int d1[26][262144];
pair<int, int> d2[2][262144];
int vis[2][262144];
long long mod = 998244353ll;
long long qpow(long long x, long long y) {
  long long a = x, ans = 1;
  while (y) {
    if (y & 1) ans = (ans * a) % mod;
    y >>= 1;
    a = (a * a) % mod;
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    G[u].push_back(make_pair(v, 0));
    G[v].push_back(make_pair(u, 1));
  }
  queue<pair<int, int>> q;
  q.push(make_pair(0, 1));
  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= 25; j++) d1[j][i] = -1;
  d1[0][1] = 0;
  while (!q.empty()) {
    pair<int, int> top = q.front();
    q.pop();
    int flips = top.first, u = top.second;
    for (auto i : G[u]) {
      int v = i.first, f = i.second;
      int flip = ((flips & 1) ^ f);
      if (flips + flip > 25) continue;
      if (d1[flips + flip][v] == -1) {
        d1[flips + flip][v] = d1[flips][u] + 1;
        q.push(make_pair(flips + flip, v));
      }
    }
  }
  int ans = 2100000000;
  for (int j = 0; j <= 25; j++)
    if (d1[j][n] != -1) {
      ans = min(ans, (1 << j) - 1 + d1[j][n]);
    }
  if (ans < 2100000000) {
    cout << ans << endl;
    return 0;
  }
  priority_queue<pair<pair<int, int>, pair<int, int>>> q2;
  q2.push(make_pair(make_pair(0, 0), make_pair(0, 1)));
  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= 1; j++) d2[j][i] = make_pair(2100000000, 2100000000);
  d2[0][1] = make_pair(0, 0);
  while (!q2.empty()) {
    pair<pair<int, int>, pair<int, int>> top = q2.top();
    q2.pop();
    int flipsbit = top.second.first, u = top.second.second;
    if (vis[flipsbit][u]) continue;
    vis[flipsbit][u] = 1;
    int flips = d2[flipsbit][u].first, dist = d2[flipsbit][u].second;
    for (auto i : G[u]) {
      int v = i.first, f = i.second;
      int flip = (flipsbit ^ f);
      int vflipsbit = ((flips + flip) & 1);
      pair<int, int> dv = make_pair(flips + flip, dist + 1);
      if (d2[vflipsbit][v] > dv) {
        d2[vflipsbit][v] = dv;
        q2.push(make_pair(make_pair(-dv.first, -dv.second),
                          make_pair(vflipsbit, v)));
      }
    }
  }
  int flips = d2[0][n].first, dist = d2[0][n].second;
  if (d2[1][n].first < d2[0][n].first) {
    flips = d2[1][n].first, dist = d2[1][n].second;
  }
  long long ans2 = (qpow(2, flips) + dist - 1) % mod;
  cout << ans2 << endl;
}
