#include <bits/stdc++.h>
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
const int dx8[] = {-1, 0, 1, 0, 1, 1, -1, -1};
const int dy8[] = {0, -1, 0, 1, 1, -1, 1, -1};
vector<long long> pow1;
vector<bool> vis[19];
void pre(long long m) {
  m += 10;
  pow1 = vector<long long>(m + 1, 1);
  for (long long i = 1; i <= m; i++) {
    pow1[i] = pow1[i - 1] * 2;
    pow1[i] %= 998244353;
  }
}
long long solve() {
  long long n, m;
  cin >> n >> m;
  pre(m);
  vector<vector<pair<long long, long long>>> g(n);
  while (m--) {
    long long a, b;
    cin >> a >> b;
    a--, b--;
    g[a].push_back({b, 1});
    g[b].push_back({a, 0});
  }
  for (long long i = 0; i <= 18; i++) {
    vis[i] = vector<bool>(n, false);
  }
  priority_queue<
      pair<pair<long long, long long>, pair<long long, long long>>,
      vector<pair<pair<long long, long long>, pair<long long, long long>>>,
      greater<pair<pair<long long, long long>, pair<long long, long long>>>>
      pq;
  pq.push({{0, 0}, {0, 0}});
  while (!pq.empty()) {
    auto x = pq.top();
    pq.pop();
    long long cost = x.first.first, u = x.first.second, a = x.second.first,
              b = x.second.second;
    if (u == n - 1) {
      return cost % 998244353;
    }
    if (vis[b][u]) continue;
    vis[b][u] = true;
    for (auto temp : g[u]) {
      long long new_c = cost;
      long long v = temp.first, is = temp.second;
      long long new_b = b;
      if ((b + is) % 2 == 0) new_b++;
      if (new_b > 18) continue;
      if (vis[new_b][v]) continue;
      new_c++;
      if (b != new_b) {
        new_c += pow1[b];
      }
      pq.push({{new_c, v}, {a, new_b}});
    }
  }
  priority_queue<pair<pair<long long, long long>, long long>,
                 vector<pair<pair<long long, long long>, long long>>,
                 greater<pair<pair<long long, long long>, long long>>>
      pq1;
  vector<bool> vis1[2];
  vis1[0] = vector<bool>(n);
  vis1[1] = vector<bool>(n);
  pq1.push({{0, 0}, 0});
  while (!pq1.empty()) {
    auto x = pq1.top();
    pq1.pop();
    long long b = x.first.first, a = x.first.second, u = x.second;
    if (u == n - 1) {
      long long ans = (pow1[b] + a - 1) % 998244353;
      return ans;
    }
    if (vis1[b % 2][u]) continue;
    vis1[b % 2][u] = true;
    for (auto temp : g[u]) {
      long long v = temp.first, is = temp.second;
      long long new_b = b;
      if ((b + is) % 2 == 0) new_b++;
      if (vis1[new_b % 2][v]) continue;
      pq1.push({{new_b, a + 1}, v});
    }
  }
  return -1;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout << solve() << '\n';
}
