問題

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

u\vec{u}^\topu\vec{u} の転置 (u1u2un)\begin{pmatrix}u_1 \\ u_2 \\ \vdots \\ u_n\end{pmatrix} を表します。

制約

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

入力

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

n kn \ k\\ u1 u2  unu_1 \ u_2 \ \dots \ u_n\\ v1 v2  vnv_1 \ v_2 \ \dots \ v_n

出力

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

入出力例

例 1

入力
3 1
0 1 2
-4 0 0
出力
7

(012)(400)=(000400800)\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} より、求める 00 の個数は 77 です。

例 2

入力
3 10
0 1 2
-4 0 0
出力
9

(012)(400)=(000400800)\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}1010 乗した行列は全ての要素が 00 となるため、求める 00 の個数は 99 です。

例 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

提出


Go (1.21)