#include <bits/stdc++.h>
using namespace std;
const int P = 998244353;
int n, m;
int A[200036];
vector<int> G[2][200036];
int dis[2][200036][19], vis[2][200036][19];
struct tcurts {
  int t, u, k;
  bool operator<(const tcurts& x) const { return 0; }
};
priority_queue<pair<int, tcurts>> Q;
priority_queue<pair<pair<int, int>, pair<int, int>>> q;
pair<int, int> ds[2][200036];
int vs[2][200036];
void solve() {
  cin >> n >> m;
  for (int i = (1), iend = (m); i <= iend; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    G[0][u].push_back(v), G[1][v].push_back(u);
  }
  memset(dis, 0x3f, sizeof dis);
  dis[0][1][0] = 0;
  Q.push(make_pair(0, tcurts{0, 1, 0}));
  while (!Q.empty()) {
    int u = Q.top().second.u, t = Q.top().second.t, k = Q.top().second.k;
    Q.pop();
    if (vis[t][u][k]) continue;
    vis[t][u][k] = 1;
    if (k <= 17 && dis[t ^ 1][u][k + 1] > dis[t][u][k] + (1 << k))
      dis[t ^ 1][u][k + 1] = dis[t][u][k] + (1 << k),
                        Q.push(make_pair(-dis[t ^ 1][u][k + 1],
                                         (tcurts){t ^ 1, u, k + 1}));
    for (int v : G[t][u]) {
      if (dis[t][v][k] > dis[t][u][k] + 1)
        dis[t][v][k] = dis[t][u][k] + 1,
        Q.push(make_pair(-dis[t][v][k], (tcurts){t, v, k}));
    }
  }
  int as = 0x3f3f3f3f;
  for (int t = (0), tend = (1); t <= tend; ++t)
    for (int k = (1), kend = (18); k <= kend; ++k) as = min(as, dis[t][n][k]);
  if (as > 1e9) {
    memset(ds, 0x3f, sizeof ds);
    ds[0][1] = make_pair(0, 0);
    q.push(make_pair(make_pair(0, 0), make_pair(0, 1)));
    while (!q.empty()) {
      int t = q.top().second.first, u = q.top().second.second;
      q.pop();
      if (vs[t][u]) continue;
      vs[t][u] = 1;
      if (ds[t ^ 1][u] > make_pair(ds[t][u].first + 1, ds[t][u].second))
        ds[t ^ 1][u] = make_pair(ds[t][u].first + 1, ds[t][u].second),
               q.push(make_pair(
                   make_pair(-ds[t ^ 1][u].first, -ds[t ^ 1][u].second),
                   make_pair(t ^ 1, u)));
      for (int v : G[t][u])
        if (ds[t][v] > make_pair(ds[t][u].first, ds[t][u].second + 1))
          ds[t][v] = make_pair(ds[t][u].first, ds[t][u].second + 1),
          q.push(make_pair(make_pair(-ds[t][v].first, -ds[t][v].second),
                           make_pair(t, v)));
    }
    pair<int, int> x = min(ds[0][n], ds[1][n]);
    as = 0;
    for (int t = (1), tend = (x.first); t <= tend; ++t) as = (as << 1 | 1) % P;
    as = (as + x.second) % P;
    printf("%d\n", as);
  } else
    printf("%d\n", as);
}
signed main() { solve(); }
