#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, L = 19, mod = 998244353;
const long long inf = 1e18 + 42;
vector<pair<int, int>> g[N * L * 2];
long long dist[N * L * 2];
void dijkstra(int s, int n);
int get(int u, int t, int p);
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    for (int t = 0; t < L; ++t) {
      g[get(u, t, 0)].push_back({1, get(v, t, 0)});
      g[get(v, t, 1)].push_back({1, get(u, t, 1)});
      g[get(u, t, 1)].push_back({(1 << t) + 1, get(v, min(L - 1, t + 1), 0)});
      g[get(v, t, 0)].push_back({(1 << t) + 1, get(u, min(L - 1, t + 1), 1)});
    }
  }
  dijkstra(get(0, 0, 0), n * L * 2);
  long long ans = inf;
  for (int t = 0; t < L - 1; ++t) {
    for (int p = 0; p < 2; ++p) {
      ans = min(ans, dist[get(n - 1, t, p)]);
    }
  }
  if (ans < inf) {
    cout << ans % mod << '\n';
  } else {
    pair<long long, long long> best = {n + 1, 0};
    for (int p = 0; p < 2; ++p) {
      long long tmp = dist[get(n - 1, L - 1, p)];
      tmp -= ((1 << (L - 1)) - 1);
      long long cand_steps = tmp / (1 << (L - 1));
      pair<long long, long long> cand = {cand_steps,
                                         dist[get(n - 1, L - 1, p)]};
      best = min(best, cand);
    }
    ans = best.second;
    ans -= best.first * (1 << (L - 1));
    ans %= mod;
    long long p2 = (1 << (L - 1));
    while (best.first--) {
      ans = (ans + p2) % mod;
      p2 = (2 * p2) % mod;
    }
    cout << ans << '\n';
  }
}
void dijkstra(int s, int n) {
  for (int i = 0; i < n; ++i) {
    dist[i] = inf;
  }
  priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                 greater<pair<long long, int>>>
      q;
  dist[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    auto cur = q.top();
    q.pop();
    int u = cur.second;
    if (dist[u] != cur.first) {
      continue;
    }
    for (auto& e : g[u]) {
      int v = e.second, w = e.first;
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        q.push({dist[v], v});
      }
    }
  }
}
int get(int u, int t, int p) { return (u * 2 * L) + (t * 2) + p; }
