시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 2048 MB6137829.630%

문제

You are given a set $S$ containing $N$ different positive integers. You are also given a positive integer $K$ and a prime number $M$.

An array is said to be honourable if each of its elements is in $S$, and the product of all elements in the array is $K$ modulo $M$.

For a given integer $L$, count the number of different honourable arrays with length $L$. Two arrays of length $L$ are said to be different if there exists an index such that the elements in both arrays differ at that index. Output the count modulo $998244353$.

입력

The first line contains four integers $N$, $K$, $M$, and $L$ ($1 \leq N, K < M$; $2 \leq M \leq 100000$; $1 \leq L \leq 10^9$; $M$ is a prime). The second line contains $N$ different integers representing $S$, each is a positive integer less than $M$.

출력

Output an integer representing the number of different honourable arrays modulo $998244353$.

예제 입력 1

2 1 3 4
1 2

예제 출력 1

8

예제 입력 2

2 1 3 1000
1 2

예제 출력 2

510735315

노트

Explanation of Sample 1: the different honourable arrays of size $4$ are: $[1, 1, 1, 1]$, $[1, 1, 2, 2]$, $[1, 2, 1, 2]$, $[1, 2, 2, 1]$, $[2, 1, 1, 2]$, $[2, 1, 2, 1]$, $[2, 2, 1, 1]$, $[2, 2, 2, 2]$.