#include <bits/stdc++.h>   using namespace std;   int n, m;   vector<pair<int, int>> G[262144];   int d1[26][262144];   pair<int, int> d2[2][262144];   int vis[2][262144];   long long mod = 998244353ll;   long long qpow(long long x, long long y) {     long long a = x, ans = 1;     while (y) {       if (y & 1) ans = (ans * a) % mod;       y >>= 1;       a = (a * a) % mod;     }     return ans;   }   int main() {     ios::sync_with_stdio(false);     cin.tie(0);     cin >> n >> m;     for (int i = 0; i < m; i++) {       int u, v;       cin >> u >> v;       G[u].push_back(make_pair(v, 0));       G[v].push_back(make_pair(u, 1));     }     queue<pair<int, int>> q;     q.push(make_pair(0, 1));     for (int i = 1; i <= n; i++)       for (int j = 0; j <= 25; j++) d1[j][i] = -1;     d1[0][1] = 0;     while (!q.empty()) {       pair<int, int> top = q.front();       q.pop();       int flips = top.first, u = top.second;       for (auto i : G[u]) {         int v = i.first, f = i.second;         int flip = ((flips & 1) ^ f);         if (flips + flip > 25) continue;         if (d1[flips + flip][v] == -1) {           d1[flips + flip][v] = d1[flips][u] + 1;           q.push(make_pair(flips + flip, v));         }       }     }     int ans = 2100000000;     for (int j = 0; j <= 25; j++)       if (d1[j][n] != -1) {         ans = min(ans, (1 << j) - 1 + d1[j][n]);       }     if (ans < 2100000000) {       cout << ans << endl;       return 0;     }     priority_queue<pair<pair<int, int>, pair<int, int>>> q2;     q2.push(make_pair(make_pair(0, 0), make_pair(0, 1)));     for (int i = 1; i <= n; i++)       for (int j = 0; j <= 1; j++) d2[j][i] = make_pair(2100000000, 2100000000);     d2[0][1] = make_pair(0, 0);     while (!q2.empty()) {       pair<pair<int, int>, pair<int, int>> top = q2.top();       q2.pop();       int flipsbit = top.second.first, u = top.second.second;       if (vis[flipsbit][u]) continue;       vis[flipsbit][u] = 1;       int flips = d2[flipsbit][u].first, dist = d2[flipsbit][u].second;       for (auto i : G[u]) {         int v = i.first, f = i.second;         int flip = (flipsbit ^ f);         int vflipsbit = ((flips + flip) & 1);         pair<int, int> dv = make_pair(flips + flip, dist + 1);         if (d2[vflipsbit][v] > dv) {           d2[vflipsbit][v] = dv;           q2.push(make_pair(make_pair(-dv.first, -dv.second),                             make_pair(vflipsbit, v)));         }       }     }     int flips = d2[0][n].first, dist = d2[0][n].second;     if (d2[1][n].first < d2[0][n].first) {       flips = d2[1][n].first, dist = d2[1][n].second;     }     long long ans2 = (qpow(2, flips) + dist - 1) % mod;     cout << ans2 << endl;   }   