sparse or not

問題

$n$ 次元の行ベクトル $\vec{u} = (u_1, u_2, \dots, u_n), \, \vec{v} = (v_1, v_2, \dots, v_n)$ と正の整数 $k$ が与えられます。$n \times n$ 行列 $(\vec{u}^\top \vec{v})^k$ の要素のうち、$0$ であるものの個数を求めてください。

$\vec{u}^\top$ は $\vec{u}$ の転置 $\begin{pmatrix}u_1 \\ u_2 \\ \vdots \\ u_n\end{pmatrix}$ を表します。

制約

• $1 \leq n \leq 3 \times 10^5$
• $1 \leq k \leq 10^9$
• $\lvert u_i \rvert \leq 10^6 \hspace{0.3em} (\mathrm{for} \ 1 \leq i \leq n)$
• $\lvert v_i \rvert \leq 10^6 \hspace{0.3em} (\mathrm{for} \ 1 \leq i \leq n)$
• 入力は全て整数

入力

入力は標準入力から以下の形式で与えられます。

出力

問題の答えを標準出力に出力してください。

入出力例

例 1

3 1
0 1 2
-4 0 0

7

$\begin{pmatrix}0 \\ 1 \\ 2\end{pmatrix} \begin{pmatrix}-4 & 0 & 0\end{pmatrix} = \begin{pmatrix}0 & 0 & 0\\ -4 & 0 & 0 \\ -8 & 0 & 0\end{pmatrix}$ より、求める $0$ の個数は $7$ です。

例 2

3 10
0 1 2
-4 0 0

9

$\begin{pmatrix}0 \\ 1 \\ 2\end{pmatrix} \begin{pmatrix}-4 & 0 & 0\end{pmatrix} = \begin{pmatrix}0 & 0 & 0\\ -4 & 0 & 0 \\ -8 & 0 & 0\end{pmatrix}$ を $10$ 乗した行列は全ての要素が $0$ となるため、求める $0$ の個数は $9$ です。

例 3

1 4
2
-2

0

例 4

32 19
-13699 -3979 0 -36322 -41682 -59976 -95756 18850 65543 36711 77362 -20053 26682 -50531 0 -81945 46356 -85638 -52312 25462 47893 -81086 88224 -61133 -20964 55553 -69852 -84006 -60646 -23686 -87149 19487
-91594 -48022 -49368 -80022 -71533 11696 11127 11687 -10397 -79284 -90586 0 -31655 -10128 93468 -22952 -17927 -32621 -21006 73914 -56260 -258 -15423 36802 0 57619 -80453 81613 32278 61678 0 326

154