先不考虑x出现的数量为偶数这个条件，用动态规划

状态表示：$f[i][j]$ 表示从$S$到$j$经过$i$条边的所有方案的数量

状态划分：$f[i + 1][j] += f[i][k]$, $k$是所有j能到的点

初始化：$f[0][S] = 1$

答案:$f[K][T]$

考虑x为偶数这个条件，多了一个限制，状态就要多一维

状态表示：$f[i][j][x]$表示从$S$到$j$经过$i$条边，并且经过$X$的次数模$2$的余数为$x$的所有方案的数量

状态划分：

1. 当$j$不为$X$时，$f[i + 1][j][x] += f[i][k][x]$, $k$是所有j能到的点

2. 当$j$为$X$时，$f[i + 1][j][x] += f[i][k][(x+1)$

初始化：$f[0][S][0] = 1$

答案:$f[K][T][0]$

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 2010, M = N * 2;
LL mod = 998244353;
int h[N], e[M], ne[M], idx;
vector<int> g[N];
LL f[N][N][2];

void add(int a, int b) { g[a].push_back(b); }

int main() {
    int n, m, k, S, T, X;
    cin >> n >> m >> k >> S >> T >> X;
    while (m--) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }

    f[0][S][S == X] = 1;
    for (int i = 0; i <= k; i++)
        for (int j = 1; j <= n; j++)
            for (int x = 0; x < 2; x++) {
                for (int k : g[j]) {
                    if (j != X)
                        f[i + 1][j][x] = ((LL)f[i + 1][j][x] + f[i][k][x]) % mod;
                    else
                        f[i + 1][j][x] = ((LL)f[i + 1][j][x] + f[i][k][(x + 1) % 2]) % mod;
                }
            }
    cout << f[k][T][0];
    return 0;
}