#include <bits/stdc++.h>
using namespace std;
long long MOD = 998244353;
const int MAXN = 200005, k = 20;
vector<long long> g[MAXN];
long long INF = 9e18;
pair<int, int> operator+(pair<int, int> a, pair<int, int> b) {
  return (pair<int, int>){a.first + b.first, a.second + b.second};
}
vector<pair<int, pair<int, int>>> gr[k * MAXN];
pair<int, int> dist[k * MAXN];
void dijkstra(int x) {
  memset(dist, -1, sizeof(dist));
  priority_queue<pair<pair<int, int>, int>> q;
  dist[x] = {0, 0};
  q.push({{0, 0}, x});
  while (!q.empty()) {
    x = q.top().second;
    pair<int, int> c = {-q.top().first.first, -q.top().first.second};
    q.pop();
    if (dist[x] != c) continue;
    for (int i = 0, ggdem = gr[x].size(); i < ggdem; ++i) {
      int y = gr[x][i].first;
      pair<int, int> c = gr[x][i].second;
      if (dist[y].first < 0 || dist[x] + c < dist[y])
        dist[y] = dist[x] + c, q.push({{-dist[y].first, -dist[y].second}, y});
    }
  }
}
long long fpow(long long b, long long e) {
  long long res = 1;
  while (e) {
    if (e & 1) res = res * b % MOD;
    b = b * b % MOD, e >>= 1;
  }
  return res;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n, m;
  cin >> n >> m;
  for (int i = 0, ggdem = m; i < ggdem; ++i) {
    long long u, v;
    cin >> u >> v;
    u--;
    v--;
    g[u].push_back(v);
  }
  for (int i = 0, ggdem = k; i < ggdem; ++i) {
    for (int j = 0, ggdem = n; j < ggdem; ++j) {
      for (auto ii : g[j]) {
        if (i & 1) {
          gr[i * n + ii].push_back({i * n + j, {0, 1}});
        } else {
          gr[i * n + j].push_back({i * n + ii, {0, 1}});
        }
      }
    }
  }
  for (int i = 0, ggdem = k - 1; i < ggdem; ++i) {
    for (int j = 0, ggdem = n; j < ggdem; ++j) {
      gr[i * n + j].push_back({(i + 1) * n + j, {0, 1 << i}});
    }
  }
  dijkstra(0);
  long long res = INF;
  for (int i = 0, ggdem = k; i < ggdem; ++i) {
    if (dist[i * n + n - 1].first != -1)
      res = min(res, (long long)dist[i * n + n - 1].second);
  }
  if (res != INF) {
    cout << res % MOD << "\n";
    return 0;
  }
  for (int i = 0, ggdem = k * n; i < ggdem; ++i) gr[i].clear();
  for (int i = 0, ggdem = 2; i < ggdem; ++i) {
    for (int j = 0, ggdem = n; j < ggdem; ++j) {
      for (auto ii : g[j]) {
        if (i & 1) {
          gr[i * n + ii].push_back({i * n + j, {0, 1}});
        } else {
          gr[i * n + j].push_back({i * n + ii, {0, 1}});
        }
      }
    }
  }
  for (int i = 0, ggdem = 2; i < ggdem; ++i) {
    for (int j = 0, ggdem = n; j < ggdem; ++j) {
      gr[i * n + j].push_back({(i ^ 1) * n + j, {1, 0}});
    }
  }
  dijkstra(0);
  auto resf = min(dist[n - 1], dist[n + n - 1]);
  res = (fpow(2, resf.first) + resf.second + MOD - 1) % MOD;
  cout << res << "\n";
  return 0;
}
