#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("-ffloat-store")
using namespace std;
const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403() {}
const long long int INF = 0xFFFFFFFFFFFFFFFL;
long long int seed;
mt19937 rng(seed = chrono::steady_clock::now().time_since_epoch().count());
inline long long int rnd(long long int l = 0, long long int r = INF) {
  return uniform_int_distribution<long long int>(l, r)(rng);
}
class CMP {
 public:
  bool operator()(pair<long long int, long long int> a,
                  pair<long long int, long long int> b) {
    return !(a.first < b.first || (a.first == b.first && a.second <= b.second));
  }
};
void add(map<long long int, long long int> &m, long long int x,
         long long int cnt = 1) {
  auto jt = m.find(x);
  if (jt == m.end())
    m.insert({x, cnt});
  else
    jt->second += cnt;
}
void del(map<long long int, long long int> &m, long long int x,
         long long int cnt = 1) {
  auto jt = m.find(x);
  if (jt->second <= cnt)
    m.erase(jt);
  else
    jt->second -= cnt;
}
bool cmp(const pair<long long int, long long int> &a,
         const pair<long long int, long long int> &b) {
  return a.first < b.first || (a.first == b.first && a.second < b.second);
}
const long long int mod = 998244353LL;
const long long int logN = 18;
long long int po(long long int a, long long int n) {
  if (n == 0) return 1;
  if (n % 2) return (a * po(a, n - 1)) % mod;
  return po(a * a % mod, n / 2);
}
long long int T, n, i, j, k, in, cnt, l, r, u, v, x, y;
long long int m;
string s;
vector<vector<pair<long long int, long long int> > > e, e2;
vector<pair<long long int, long long int> > d2;
void run(const vector<vector<pair<long long int, long long int> > > &e) {
  auto cmp = [](const pair<long long int, long long int> &a,
                const pair<long long int, long long int> &b) {
    return !(a.first < b.first || (a.first == b.first && a.second <= b.second));
  };
  priority_queue<pair<long long int, long long int>,
                 vector<pair<long long int, long long int> >, decltype(cmp)>
      pq(cmp);
  pq.push({0, 0});
  ;
  vector<long long int> dist(logN * n, INF);
  while (!pq.empty()) {
    auto d = pq.top().first, u = pq.top().second;
    pq.pop();
    if (dist[u] <= d) continue;
    dist[u] = d;
    for (auto x : e[u]) pq.push({x.second + d, x.first});
  }
  long long int ans = INF;
  for (long long int i = 0; i < logN; i++) ans = min(ans, dist[i * n + n - 1]);
  if (ans < INF) {
    cout << ans % mod << "\n";
    exit(0);
  };
  const long long int offset = (logN - 2) * n;
  for (long long int i = offset; i < logN * n; ++i) {
    if (dist[i] < INF) d2[i - offset] = {logN - 1, dist[i] - (1LL << logN) / 2};
  }
}
void run2(const vector<vector<pair<long long int, long long int> > > &e) {
  auto cmp =
      [](const pair<pair<long long int, long long int>, long long int> &a,
         const pair<pair<long long int, long long int>, long long int> &b) {
        return !(a.first < b.first ||
                 (a.first == b.first && a.second <= b.second));
      };
  priority_queue<
      pair<pair<long long int, long long int>, long long int>,
      vector<pair<pair<long long int, long long int>, long long int> >,
      decltype(cmp)>
      pq(cmp);
  for (long long int i = 0; i < 2 * n; ++i) pq.push({d2[i], i});
  ;
  vector<pair<long long int, long long int> > dist(2 * n, {INF, INF});
  while (!pq.empty()) {
    auto d = pq.top().first;
    auto u = pq.top().second;
    pq.pop();
    if (dist[u] <= d) continue;
    dist[u] = d;
    for (auto x : e[u]) {
      if (x.second > 0)
        pq.push({{d.first, d.second + 1}, x.first});
      else
        pq.push({{d.first + 1, d.second}, x.first});
    }
  };
  pair<long long int, long long int> ans = min(dist[n - 1], dist[2 * n - 1]);
  ;
  cout << (po(2, ans.first) + ans.second) % mod << "\n";
}
int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  {
    cin >> n >> m;
    e.resize(logN * n);
    e2.resize(2 * n);
    d2.resize(2 * n, {INF, INF});
    while (m--) {
      cin >> u >> v;
      u--;
      v--;
      for (long long int i = 0; i < logN; i++) {
        e[i * n + u].push_back({i * n + v, 1});
        i++;
        e[i * n + v].push_back({i * n + u, 1});
      }
      e2[u].push_back({v, 1});
      e2[n + v].push_back({n + u, 1});
    }
    for (long long int i = 0; i + 1 < logN; i++)
      for (long long int u = 0; u < n; ++u)
        e[i * n + u].push_back({i * n + u + n, 1 << i});
    for (long long int u = 0; u < n; ++u) {
      e2[u].push_back({u + n, -1});
      e2[u + n].push_back({u, -1});
    }
    run(e);
    run2(e2);
  }
  aryanc403();
  return 0;
}
