#include <bits/stdc++.h>   using ll = long long;   using ld = long double;   using ull = unsigned long long;   using namespace std;   const int N = 2e5 + 2, mod = 998244353;   int n, m, d[N][20];   pair<int, int> dist[N][2];   vector<int> g[2][N];   struct State {     int d, ver, B;     bool operator<(const State& oth) const { return d > oth.d; }   };   struct State1 {     int B, A, ver;     bool operator<(const State1& oth) const {       return B > oth.B || (B == oth.B && A > oth.A);     }   };   void solve1() {     priority_queue<State1> pq;     for (int i = (1); i <= (n); ++i) dist[i][0] = dist[i][1] = {1e9, 1e9};     dist[1][0] = {0, 0};     pq.push({0, 0, 1});     while (!pq.empty()) {       State1 cur = pq.top();       pq.pop();       int side = cur.B & 1;       if (pair<int, int>(cur.B, cur.A) != dist[cur.ver][side]) continue;       for (int v : g[side][cur.ver])         if (dist[v][side].first > cur.B ||             (dist[v][side].first == cur.B && dist[v][side].second > cur.A + 1)) {           dist[v][side] = {cur.B, cur.A + 1};           pq.push({cur.B, cur.A + 1, v});         }       if (dist[cur.ver][side ^ 1].first > cur.B + 1 ||           (dist[cur.ver][side ^ 1].first == cur.B + 1 &&            dist[cur.ver][side ^ 1].second > cur.A)) {         dist[cur.ver][side ^ 1] = {cur.B + 1, cur.A};         pq.push({cur.B + 1, cur.A, cur.ver});       }     }     pair<int, int> ans = dist[n][0];     if (dist[n][1].first < ans.first ||         (dist[n][1].first == ans.first && dist[n][1].second < ans.second))       ans = dist[n][1];     assert(ans.first != 1e9 && ans.second != 1e9);     int res = 1;     for (int i = (1); i <= (ans.first); ++i) res = res * 2LL % mod;     cout << (res + ans.second - 1) % mod;   }   void solve() {     int LG = 32 - __builtin_clz(m);     assert(LG <= 19);     priority_queue<State> pq;     pq.push({0, 1, 0});     for (int i = (1); i <= (n); ++i)       for (int j = (0); j <= (19); ++j) d[i][j] = 1e9;     d[1][0] = 0;     while (!pq.empty()) {       State cur = pq.top();       pq.pop();       if (cur.d != d[cur.ver][cur.B]) continue;       for (int v : g[cur.B & 1][cur.ver])         if (d[v][cur.B] > cur.d + 1) {           d[v][cur.B] = cur.d + 1;           pq.push({d[v][cur.B], v, cur.B});         }       if (cur.B < LG) {         if (d[cur.ver][cur.B + 1] > cur.d + (1 << cur.B)) {           d[cur.ver][cur.B + 1] = cur.d + (1 << cur.B);           pq.push({d[cur.ver][cur.B + 1], cur.ver, cur.B + 1});         }       }     }     int ans = 1e9;     for (int i = (0); i <= (LG); ++i)       if (ans > d[n][i]) ans = d[n][i];     if (ans == 1e9)       solve1();     else       cout << ans;   }   int main() {     ios_base::sync_with_stdio(false);     cin.tie(nullptr);     cin >> n >> m;     for (int i = (1); i <= (m); ++i) {       int u, v;       cin >> u >> v;       g[0][u].emplace_back(v);       g[1][v].emplace_back(u);     }     solve();     return 0;   }   