問題文

素数 $p$ と整数 $a_1,a_2,\dots ,a_n$, $k$, $b$ が与えられます。$a_1{x}_1^k+a_2{x}_2^k+\cdots +a_n{x}_n^k$ を $p$ で割った余りが $b$ であるような、$0$ 以上 $p-1$ 以下の整数の組 $(x_1,x_2,\dots ,x_n)$ は何個あるでしょうか。答えは大きくなりうるので、${10}^9+7$ で割った余りを求めてください。

入力

$pnkb$
$a_1{a}_2\dots a_n$

• $2\le p\le {10}^5$
• $p$ は素数である。
• $1\le n\le 500$
• $1\le k\le {10}^5$
• $0\le b\le p-1$
• $0\le a_i\le p-1$
• 入力はすべて整数である。

出力

条件を満たす整数の組の個数を ${10}^9+7$ で割った余りを出力せよ。

サンプル

3 3 2 2
1 1 2

6

7 5 3 6
3 1 4 1 5

2373

10007 1 314 159
0

0