I used a kind of dp.

Keep arrays oddArr and evenArr of size n+1 to hold the number of sequences (mod P) of a given length ending at each node. evenArr contains the number of sequences having an even number of the node X, oddArr an odd number of X. At first the sequence only contains S (not equal to X) so you initialize evenArr[S]=1 (number of X = 0 is even; oddArr is all 0 and the rest of evenArr is also 0).

Then you simulate the graph, increasing the sequence length from 1 to K+1 (K iterations). At each iteration update oddArr and evenArr (using temp arrays newOddArr and newEvenArr to hold the data for the next iteration) by looping on each node i of the graph and on each neighbor j of i (the second loop only if oddArr[i]>0 or evenArr[i]>0) and summing. If j==X, newEvenArr[j] += oddArr[i] (mod P) and newOddArr[j] += evenArr[i] (because the parity of the number of X changes). Otherwise, newEvenArr[j] += evenArr[i] and newOddArr[j] += oddArr[i] (no parity change).

The answer is evenArr[T] (number of sequences of length K+1 mod P starting at S ending at T with even number of X).

First of all, convince yourself that this problem can be solved using Dynamic Programming(there are a lot of hints in the problem statement hinting towards DP — number of sequences, % by 998244353, etc.,).

Then there are a few constraints in the problem, like our sequence should start with a value s and end with a value t so the first and the last values are fixed no matter which sequence we build.

The other constraint is that all 1 <= Ai <= N. This will be taken care of automatically since the input graph contains only vertices with values in the range [1, N].

The next constraint is that the adjacent elements in any sequence we build should be edges in our graph. So, when building the sequence step by step, we only traverse through the edges of the current node, and the next element of the sequence will be some direct child of the current node.

The last thing(another constraint) we need to take care of is that we are given a value x and in any sequence we build, the frequency of x should be even.

Now, let's try to define a state for our Dynamic Programming solution.

So, the necessary parameters which are required to decide what the next element of our sequence can be and if the sequence we have built is a valid sequence or not are the following:

1. the current index we are at when building the sequence (this will help us to construct a sequence of length only K and nothing else)

2. what was the previous element in our sequence (this will help us to make sure that the adjacent elements in our sequence are edges in the given graph)

3. frequency of the value x

Let's name these parameters and define a DP state.

State: dp(i, prev, freq) = Number of sequences built using the first i elements such that the previous element was prev and the frequency of x in the current sequence is x(This definition will vary according to the implementation)

How to compute the answer for any state?

Remember the constraints? Always remember the constraints when thinking about the transitions. In this case, it is helpful to think about how we'll build a sequence step by step. For example, if we are at index 2 and let's say the current value A2 is 3. Also, let's assume node 3 is connected with nodes 4 and 5 in the graph. Then the next element of our sequence can be either 4 or 5. So, we have two possibilities. Similarly, for all indices i. Hence, from any node prev we can go to any child node of prev i.e., any node in adj[prev](adj[prev] contains a list of nodes that are directly connected to the node prev).

Also, we need to keep track of the frequency of the value x.

What will be the answer to the whole problem?

answer: dp(0, s, any_even_frequency_of_x) (it's dp(0, .., ..) because we'll be using dp(i + 1) to update dp(i) unlike using dp(i — 1) to update dp(i). So, this is just an implementation detail).

What will be the base case of the problem?

base case: when i is k, return 1 iff prev is t and the frequency_of_x is even, else return 0(This should be obvious as we want to count the number of sequences we are returning 1).

Now that we have looked at the state, transition, answer, and the base case. Let's see what is the runtime of our approach.

1. There are K indices.
2. There are N prev nodes.
3. There are be M edges(So, moving from one node to another node can be done in O(N + M) similar to DFS. This part might not be clear at the first time. So, try proving it or refer to the implementation to see how or why it is so).
4. There can be at most K / 2 values of x in our sequence(it's not K because there are no self-loops in our graph).

So, the total time complexity will be O(K * (N + M) * K / 2) which can lead to TLE for the given constraints.

Optimization

By looking at the statement Integer X appears even number of times (possibly zero) in sequence A closely, we can see that it doesn't matter what the actual frequency of x is, rather we just care about the parity of the frequency of x. i.e., the remainder of the frequency of x when divided by 2. So, instead of storing or computing all K / 2 possible frequencies of x, what we can do is only store frequency_of_x % 2. This will anyway tell us if in the final sequence x has an even or odd frequency.

Now, the time complexity becomes O(K * (N + M) * 2) which can pass the given constraints.

Submission with both top down and bottom up implementation