1769: 神奇的题目

AekdyCoin最近刚刚学了数论，于是对数论产生了极大的兴趣，现在AekdyCoin有在思考一道极难的题目了，让我们一起来看看吧！

现有一个包含n个元素的a数列，其中a1=A1,a2=A2,ai=A3*ai-2+A4*ai-1+A5(3<=i<=n)。

和另外一个包含m个元素的b数列，其中b1=B1,b2=B2,bi=B3*bi-2+B4*bi-1+B5(3<=i<=m)。

而这时AekdyCoin为了引进数列的知识，就又找了一个素数p。

现在可以从a数列中任意选择一个元素ai，从b数列中任意选择一个元素bj，而AekdyCoin的目标是使得ai*bj mod p <= k (0<=k<=p)。于是AekdyCoin开始一一验证了，结果发现这个验证过程是极其巨大的，于是AekdyCoin就想知道到底有多少对(ai,bj)满足AekdyCoin他自己给出的条件。

输入的第一行包括6个整数，分别表示n,A1,A2,A3,A4,A5。

输入的第二行也包括6个整数，分别表示m,B1,B2,B3,B4,B5。

最后一行包括2个整数分别表示p和k(0<=k<=p)。

3<=n,m<=10^6

0<= A1,A2,A3,A4,A5, B1,B2,B3,B4,B5<=10^9

2<=p<=2*10^4

30%的数据保证n,m<=1000。

50%的数据保证p<=1000。

80%的数据保证p<=5000。

100%的数据保证n,m<=10^6 和p<=2*10^4

输出只有一个数字，即满足AekdyCoin要求的元素对数。

5 0 0 1 2 2

3 2 1 1 1 1

3 2

15