#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int mul(int a, int b) { return (long long)a * b % mod; }
int add(int a, int b) {
  int res = (long long)a + b;
  if (res < 0)
    res += mod;
  else if (res > mod)
    res -= mod;
  return res;
}
int bpow(int x, int p) {
  int res = 1;
  while (p) {
    if (p & 1) res = mul(res, x);
    p >>= 1;
    if (p) x = mul(x, x);
  }
  return res;
}
void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<pair<int, int>>> g(25 * n);
  vector<vector<pair<int, int>>> g2(2 * n);
  for (int i = 0; i < m; i++) {
    int f, t;
    cin >> f >> t;
    f--;
    t--;
    for (int j = 0; j < 25; j++) {
      if (j % 2)
        g[t + j * n].push_back({f + j * n, 1});
      else
        g[f + j * n].push_back({t + j * n, 1});
    }
    g2[f].push_back({t, 0});
    g2[t + n].push_back({f + n, 0});
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 24; j++) {
      g[i + j * n].push_back({i + (j + 1) * n, 1 << j});
    }
    g2[i].push_back({i + n, 1});
    g2[i + n].push_back({i, 1});
  }
  priority_queue<pair<long long, int>> q;
  vector<long long> used(25 * n, -1);
  q.push({0, 0});
  while (q.size()) {
    auto v = q.top();
    q.pop();
    v.first *= -1;
    if (used[v.second] != -1) continue;
    used[v.second] = v.first;
    for (auto to : g[v.second]) {
      if (used[to.first] == -1) q.push({-(to.second + v.first), to.first});
    }
  }
  long long ans = 1e18;
  for (int i = 0; i < 25; i++) {
    if (used[n - 1 + i * n] != -1) ans = min(ans, used[n - 1 + i * n]);
  }
  if (ans == 1e18) ans = -1;
  if (ans != -1) {
    cout << ans % mod;
    return;
  }
  priority_queue<pair<pair<int, int>, int>> q2;
  vector<pair<int, int>> used2(2 * n, {-1, -1});
  q2.push({{0, 0}, 0});
  while (q2.size()) {
    auto v = q2.top();
    q2.pop();
    v.first.first *= -1;
    v.first.second *= -1;
    if (used2[v.second] != make_pair(-1, -1)) {
      continue;
    }
    used2[v.second] = v.first;
    for (auto to : g2[v.second]) {
      if (to.second == 0 && used2[to.first] == make_pair(-1, -1)) {
        q2.push({{-v.first.first, -v.first.second - 1}, to.first});
      } else if (used2[to.first] == make_pair(-1, -1)) {
        q2.push({{-v.first.first - 1, -v.first.second}, to.first});
      }
    }
  }
  pair<int, int> ans2 = min(used2[n - 1], used2[2 * n - 1]);
  cout << add(ans2.second, add(bpow(2, ans2.first), -1));
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int q = 1;
  for (; q > 0; q--) {
    solve();
    cout << endl;
  }
}
