The condition “integer \(X\) appears even number of times in sequence \(A\)” is a bit difficult to handle with, so let us first ignore this. Then, the question will be like: “how many ways are there to travel from Vertex \(S\) to Vertex \(T\) using edges \(K\) times?” This can be solved by DP (Dynamic Programming) just like ABC242 C - 1111gal password.

Specifically, we can compute

\(dp[i][j] = {}\)(the number of ways to travel from Vertex \(S\) to Vertex \(j\) using edges \(i\) times).

The recurrence relations are:

\(dp[0][j] = \begin{cases} 1 & (j = S) \\ 0 & (j ≠ S)\end{cases}\)
\(dp[i + 1][j] = \displaystyle\sum_{k \in \text{adj}(j)}dp[i][k]\)

where \(\text{adj}(i)\) is a set of vertices that are directly connected by edges to Vertex \(i\). \(dp[K][T]\) is the desired answer. The time complexity is \(O((N + M) K)\).

Now, in order to handle with the condition “integer \(X\) appears even number of times in sequence \(A\)”, we have to maintain the state in the DP calculation whether “it has visited Vertex \(X\) even or odd number of times.” When it visits Vertex \(X\) during the DP, we can flip the state from even to odd, or odd to even.

In order to add the state, we can add an index to \(dp\). Specifically, let

\(dp[i][j][x] = {}\)(the number of ways to travel from Vertex \(S\) to Vertex \(j\) using edges \(i\) times, in which (the number of visits to Vertex \(X\))\({}\bmod 2\) is \(x\)).

The recurrence relations are:

\(dp[0][j][0] = \begin{cases} 1 & (j = S) \\ 0 & (j ≠ S)\end{cases}\)
\(dp[0][j][1] = 0\)
\(dp[i + 1][j][x] = \displaystyle\sum_{k \in \text{adj}(j)}dp[i][k][x]\ (j ≠ X)\)
\(dp[i + 1][X][x] = \displaystyle\sum_{k \in \text{adj}(X)}dp[i][k][1 - x]\).

\(dp[K][T][0]\) is the desired answer. The time complexity is still \(O((N + M) K)\), so the problem has been solved.

In order to find the answer modulo \(998244353\), you can find the remainder by \(998244353\) after each computation, or use modint in AC Library.

Sample code (C++)

#include <atcoder/modint>
#include <array>
#include <iostream>
#include <vector>
using namespace std;
using Modint = atcoder::modint998244353;

int main(){
    int N, M, K, S, T, X;
    cin >> N >> M >> K >> S >> T >> X;
    S--; T--; X--;
    vector<pair<int, int>> edge(M);
    for(auto& [U, V] : edge){
        cin >> U >> V;
        U--; V--;
    }
    vector dp(K + 1, vector(N, array<Modint, 2>{0, 0}));
    dp[0][S][0] = 1;
    for(int i = 0; i < K; i++){
        for(auto [U, V] : edge) for(int x : {0, 1}){
            dp[i + 1][V][x ^ (V == X)] += dp[i][U][x];
            dp[i + 1][U][x ^ (U == X)] += dp[i][V][x];
        }
    }
    cout << dp[K][T][0].val() << endl;
}

Sample code (Python)

MOD = 998244353
N, M, K, S, T, X = map(int, input().split())
S -= 1
T -= 1
X -= 1

edge = []
for i in range(M):
    U, V = map(int, input().split())
    U -= 1
    V -= 1
    edge.append((U, V))

dp = [[[0] * N for i in range(K + 1)] for x in range(2)]
dp[0][0][S] = 1

for i in range(K):
    for U, V in edge:
        for x in range(2):
            dp[x][i + 1][V] += dp[x ^ (V == X)][i][U]
            if dp[x][i + 1][V] >= MOD:
                dp[x][i + 1][V] -= MOD
            dp[x][i + 1][U] += dp[x ^ (U == X)][i][V]
            if dp[x][i + 1][U] >= MOD:
                dp[x][i + 1][U] -= MOD

print(dp[0][K][T])