题目描述

给定九个整数 $N,X_0,XMul,XAdd,XMod,Y_0,YMul,YAdd,YMod$。按下面的递推生成 $N+2$ 个点 $(X[i],Y[i])$：

$X[0]=X_0$，对 $0<i<N+2$，$X[i]=(X[i-1]\times XMul+XAdd)\bmod XMod$；

$Y[0]=Y_0$，对 $0<i<N+2$，$Y[i]=(Y[i-1]\times YMul+YAdd)\bmod YMod$。

保证生成的 $N+2$ 个点两两不同，并且任意三个点不共线。

令 $S=\{(X[0],Y[0]),\ldots,(X[N-1],Y[N-1])\}$， $P=(X[N],Y[N])$，$Q=(X[N+1],Y[N+1])$。

从 $S$ 中选择一个子集 $T$。如果满足以下条件，则称 $T$ 为合法子集：

• $|T|\ge3$；
• $T$ 的凸包同时包含点 $P$ 和点 $Q$。

求合法子集数量对 $1,000,000,007$ 取模后的结果。

输入格式

一行九个整数：

N X0 XMul XAdd XMod Y0 YMul YAdd YMod

输出格式

输出一个整数，表示合法子集数量对 $1,000,000,007$ 取模后的结果。

样例

输入

4 3 3 3 10 0 3 2 7

输出

3

输入

5 1 5 6 8 5 5 3 9

输出

5

数据范围

$3\le N\le2000$；$1\le XMod,YMod\le10^8$；$0\le X_0,XMul,XAdd<XMod$；$0\le Y_0,YMul,YAdd<YMod$。保证生成点两两不同，且任意三个生成点不共线。