Description

众所周知，我们的红太阳王队长很喜欢自然数列。对于4个长度为n的自然数列\(a_1, a_2, a_3, a_4\)，一个四元组\((w,x,y,z)\)满足\(w\in a_1, x\in a_2, y\in a_3, z\in a_4\)是滑稽的，当且仅当\(w\times x\times y\times z\ mod\ p = 1\)，p为给定的素数。现在给你四个自然数列和一个素数p，请求出所有的滑稽四元组的个数。

Input

• 第一行为2个正整数n, p，表示数列长和模数。
• 接下来四行，每行\(n\)个空格隔开的自然数，第\(i+1\)行表示\(a_i\)
• 请注意，自然数列存在重复，元素相同但出现位置不同的四元组应该算多次。

Output

• 仅一个整数，表示答案

Sample

Input

3 17
1 2 3
0 0 1
2 3 3
6 6 6

Output

6

Hint

• 滑稽四元组(按出现位置为)：(1,3,2,1)，(1,3,2,2)，(1,3,2,3)，(1,3,3,1)，(1,3,3,2)，(1,3,3,3)。

• 对于5%的数据，\(n=1, p\le 70\)

• 对于另外15%的数据，\(n=70, p\le 2^{30}\)

• 对于另外10%的数据，\(p = 2\)

• 对于另外15%的数据，\(p\le 70\)

• 对于另外20%的数据，\(p\le 10^6\)

• 对于另外5%的数据，所有人持有的数字均为1

• 对于100%的数据，\(n\le 1000, q\le 2^{30}\)

Source

zrO wangyurzee7 Orz