#include <bits/stdc++.h>
using namespace std;
const int M = 2e5 + 100;
const int N = 22 * M;
const int mod = 998244353;
struct Val {
  int a;
  int b;
  Val() { a = b = 0; }
  Val(int _, int __) { a = _, b = __; }
  bool operator<(const Val &y) const {
    if (y.b <= 25 && b <= 25) return a + (1 << b) < y.a + (1 << y.b);
    if (y.b == b) return a < y.a;
    return b < y.b;
  }
  Val operator+(const Val &y) const {
    Val res;
    res.a = a + y.a;
    res.b = b + y.b;
    return res;
  }
  int get() {
    long long res = 1;
    long long x = 2;
    while (b) {
      if (b & 1) res = res * x % mod;
      x = x * x % mod;
      b >>= 1;
    }
    return ((res + a - 1) % mod + mod) % mod;
  }
};
int n, m;
Val dis[N];
vector<pair<int, Val> > G[N];
priority_queue<pair<Val, int>, vector<pair<Val, int> >,
               greater<pair<Val, int> > >
    q;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    static int u, v;
    scanf("%d%d", &u, &v);
    for (int j = 0; j <= 21; j++) {
      swap(u, v);
      G[v + j * n].push_back({u + j * n, Val(1, 0)});
      ;
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= 20; j++) {
      G[i + j * n].push_back({i + (j + 1) * n, Val(0, 1)});
    }
    G[i + 21 * n].push_back({i + 20 * n, Val(0, 1)});
  }
  memset(dis, 0x3f, sizeof(dis));
  dis[1] = Val(0, 0);
  q.push({dis[1], 1});
  while (!q.empty()) {
    int j = q.top().second;
    Val d = q.top().first;
    q.pop();
    for (auto v : G[j]) {
      if (d + v.second < dis[v.first]) {
        dis[v.first] = d + v.second;
        q.push({dis[v.first], v.first});
      }
    }
  }
  Val ans = Val(0, n + 10);
  for (int j = 0; j <= 21; j++)
    if (dis[n + j * n] < ans) ans = dis[n * j + n];
  printf("%d\n", ans.get());
}
