#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 23;
const int mod = 998244353;
const int N = 8e6 + 23;
int n, m;
vector<pair<int, int> > e;
vector<pair<int, int> > g[maxn], _g[N], G[maxn];
int d[maxn], _d[N], dis[maxn];
bool vis[maxn], _vis[N];
void add(int u, int v, int w) {
  g[u].push_back({v, w});
  G[v].push_back({u, w});
}
void _add(int u, int v, int w) { _g[u].push_back({v, w}); }
void dijkstra(int s) {
  memset(d, 0x3f, sizeof(d));
  memset(vis, 0, sizeof(vis));
  priority_queue<pair<int, int> > q;
  q.push({0, s});
  d[s] = 0;
  while (!q.empty()) {
    int x = q.top().second;
    q.pop();
    if (vis[x]) continue;
    vis[x] = 1;
    for (auto i : g[x]) {
      int y = i.first, z = i.second;
      if (d[y] > d[x] + z) {
        d[y] = d[x] + z;
        q.push({-d[y], y});
      }
    }
  }
}
void _dij(int s) {
  memset(_d, 0x3f, sizeof(_d));
  memset(_vis, 0, sizeof(_vis));
  priority_queue<pair<int, int> > q;
  q.push({0, s});
  _d[s] = 0;
  while (!q.empty()) {
    int x = q.top().second;
    q.pop();
    if (_vis[x]) continue;
    _vis[x] = 1;
    for (auto i : _g[x]) {
      int y = i.first, z = i.second;
      if (_d[y] > _d[x] + z) {
        _d[y] = _d[x] + z;
        q.push({-_d[y], y});
      }
    }
  }
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    e.push_back({u, v});
    add(u, v, 0);
    add(v + n, u + n, 0);
    add(v, u + n, 1);
    add(u + n, v, 1);
  }
  dijkstra(1);
  int rev = min(d[n], d[n + n]);
  if (rev >= 20) {
    queue<int> q;
    memset(vis, 0, sizeof(vis));
    if (d[n] == rev) q.push(n);
    if (d[n + n] == rev) q.push(n + n);
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      for (auto i : G[x]) {
        int y = i.first, z = i.second;
        if (d[y] == d[x] - z && !vis[y]) {
          vis[y] = 1;
          q.push(y);
          dis[y] = dis[x] + 1;
        }
      }
    }
    int ans = 1;
    while (rev) {
      ans *= 2;
      ans %= mod;
      rev--;
    }
    ans--;
    ans += dis[1];
    cout << (ans + mod) % mod;
    return 0;
  }
  rev = 19;
  for (auto q : e) {
    int u = q.first, v = q.second;
    for (int i = 0; i <= rev; i++) {
      if (!(i & 1)) {
        _add(u + i * n, v + i * n, 1);
      } else {
        _add(v + i * n, u + i * n, 1);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < rev; j++) _add(i + j * n, i + j * n + n, 1 << j);
  }
  _dij(1);
  int ans = 1e9;
  for (int i = 1; i <= rev; i++) ans = min(ans, _d[i * n]);
  cout << ans;
}
