Sum of Lantern Chains Beauty

Little K is hosting a lantern festival at his large house. He has n lanterns numbered from 1 to n and connects them with m directed edges. The edges ensure that if we ignore their directions the lanterns are connected, and the given directed graph is guaranteed to be acyclic. Each lantern can independently emit one of k colors.

Little K wants to try every one of the kⁿ possible assignments. He defines the beauty of a color assignment as follows. For a fixed positive integer l, a chain of length l is defined as a tuple

[ (v_1, e_1, v_2, e_2, \dots, e_{l-1}, v_l), ]

such that for every (1 \le i < l), the directed edge (e_i) goes from vertex (v_i) to vertex (v_{i+1}). Two chains are considered different if there exists at least one index where the vertices or the corresponding edges differ. For each color (x), let (cnt_x) be the number of chains of length (l) in which every lantern in the chain is colored (x) (i.e. for every (1 \le i \le l,) the lantern (v_i) emits color (x)). The beauty of an assignment is defined as

[ \sum_{x=1}^{k} cnt_x^2. ]

Your task is to compute the sum of the beauties of all kⁿ assignments modulo \(998244353\).

Input/Output Explanation

Two assignments are different if there exists at least one lantern that emits different colors in the two assignments.

inputFormat

The first line contains four integers n, m, k and l -- the number of lanterns, the number of directed edges, the number of colors and the chain length, respectively.

Then follow m lines, each containing two integers u and v, indicating a directed edge from lantern u to lantern v.

It is guaranteed that the underlying undirected graph is connected and the directed graph is acyclic.

outputFormat

Output a single integer -- the sum of all beauties modulo \(998244353\).

sample

3 2 2 2
1 2
2 3

12