#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 18;
int n, m;
pair<int, int> dist[N + 2][2][200000 + 1];
vector<int> g[2][200000 + 1];
int main() {
  scanf("%d%d", &n, &m);
  priority_queue<pair<pair<int, int>, pair<pair<int, int>, int> >,
                 vector<pair<pair<int, int>, pair<pair<int, int>, int> > >,
                 greater<pair<pair<int, int>, pair<pair<int, int>, int> > > >
      q;
  for (int i = 1; i <= m; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    g[0][u].push_back(v);
    g[1][v].push_back(u);
  }
  for (int i = 0; i <= N + 1; ++i)
    for (int j = 0; j < 2; ++j)
      for (int k = 1; k <= n; ++k) dist[i][j][k] = make_pair(INF, INF);
  dist[0][0][1] = make_pair(0, 0);
  q.push(make_pair(make_pair(0, 0), make_pair(make_pair(0, 0), 1)));
  while (!q.empty()) {
    pair<int, int> val = q.top().first;
    int i, j, k;
    i = q.top().second.first.first;
    j = q.top().second.first.second;
    k = q.top().second.second;
    q.pop();
    if (dist[i][j][k] != val) continue;
    for (auto it : g[j][k]) {
      pair<int, int> tmp = val;
      tmp.second++;
      if (tmp < dist[i][j][it]) {
        dist[i][j][it] = tmp;
        q.push(make_pair(dist[i][j][it], make_pair(make_pair(i, j), it)));
      }
    }
    val.first++;
    j ^= 1;
    for (auto it : g[j][k]) {
      pair<int, int> tmp = val;
      tmp.second++;
      if (tmp < dist[min(N + 1, val.first)][j][it]) {
        dist[min(N + 1, val.first)][j][it] = tmp;
        q.push(make_pair(dist[min(N + 1, val.first)][j][it],
                         make_pair(make_pair(min(N + 1, val.first), j), it)));
      }
    }
  }
  int rest = INF;
  for (int i = 0; i <= N; ++i) {
    for (int j = 0; j < 2; ++j) {
      rest = min(rest, dist[i][j][n].second + (1 << i) - 1);
    }
  }
  if (rest != INF) {
    cout << rest << endl;
  } else {
    int MOD = 998244353;
    dist[N + 1][0][n] = min(dist[N + 1][0][n], dist[N + 1][1][n]);
    int rest = 1;
    for (int i = 1; i <= dist[N + 1][0][n].first; ++i)
      rest = 1ll * rest * 2 % MOD;
    rest--;
    rest += dist[N + 1][0][n].second;
    rest %= MOD;
    cout << (rest + MOD) % MOD << endl;
  }
  return 0;
}
