题目描述

有q次询问，每次给出两个整数n, m，求C(n, m)。

C(n, m)表示从n个不同的物品中选出m个的方案数。

输出q次询问的结果之和，结果对10^9 + 7取模。

当i > 1时，(n_i,m_i) = (n_{i-1} \times a + b, m_{i-1} \times b + a) mod \space c

注意：当m > n时，结果为C(n, m) = 0。

输入格式

第一行三个整数q, a, b, c。(1 \le q, a, b, c \le 10^7)

第二行给出n_1, m_1，之后的询问按照题目给出的方式生成。

输出格式

一个整数，表示所有询问的结果之和。

样例输入1

10 2 7 19999
5 3

样例输出1

10