ABC 244

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M, K, S, T, X;
    cin >> N >> M >> K >> S >> T >> X;
    S--, T--, X--;
    vvint graph(N);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    // dp[k][i][j]: k 回移動後、頂点 i にたどり着くまでに頂点 X を偶数(j=0)/奇数(j=1)回訪れる経路の数
    vector<vector<vector<mint>>> dp(K + 1, vector<vector<mint>>(N, vector<mint>(2)));
    dp[0][S][0] = 1;

    rep2(i, 1, K + 1) {
        rep(j, N) {
            for (int nx : graph[j]) {
                if (nx == X) {
                    dp[i][nx][0] += dp[i - 1][j][1];
                    dp[i][nx][1] += dp[i - 1][j][0];
                } else {
                    dp[i][nx][0] += dp[i - 1][j][0];
                    dp[i][nx][1] += dp[i - 1][j][1];
                }
            }
        }
    }

    cout << dp[K][T][0].val() << endl;
}