小C是一个算法竞赛爱好者,他最擅长处理的就是序列问题。
有一天小 C 遇到了一个棘手的序列问题,与一般的序列不同,这个序列有无限长!现在有一个下标从 1 开始的无限长的序列 x1,x2,⋯。对该序列进行一次操作,会使得操作后的序列 =xi+xi+1。同时小 C 观察到这个序列一开始有一个非常优美的性质:每隔 n 个数开始循环,即 ∀i,xi=x(i−1)mod。
现在小 C 需要解决 q 个问题,每个问题开始时,序列会重置为 0。接下来,小 C 会将这个序列中所有 x_t 都赋为 1,其中 t=m_i + cn_i, c=0,1,2,\cdots 然后小 C 想知道,对这个序列操作 k_i 次后,x_{pos_i} 的值是多少?当然,多次操作后与 x_{pos_i} 的值可能过大,你只需要输出 x_{pos_i} 在模p_i 意义下的取值即可。
输入格式
第一行,包含一个数 q。
接下来一行,每行五个数 n_i, m_i, k_i, pos_i, p_i。
输出格式
输出 q 行,每行一个数,表示每个询问的答案。
样例数据
样例输入
10
4 3 2 3 9900101
5 5 5 1 9900091
6 5 1 4 9900091
40 38 14 6 9900161
46 14 31 9 9900857
49 15 33 12 9901627
390 175 377 238 9900931
335 240 466 328 9907291
2653 1204 3563 891 9911609
3872 3142 4144 1787 9908449
样例输出
1
5
1
0
169911
5456
762581
7846051
5523436
2847830
子任务
- Subtask 1(10 pts): n_i \leq 2
- Subtask 2(20 pts): n_i \leq 20
- Subtask 3(20 pts): n_i 互不相同,k_i \le 10^6,\forall i, j, p_i = p_j。
- Subtask 4(50 pts): 无特殊限制。
对于所有数据,0 \leq q \leq 500,1 \leq m_i \leq n_i \leq 10^5,\sum n_i \leq 10^6,1 \leq k_i \leq 10^9,1 \leq pos_i \leq n,p_i 为质数且 p_i \leq 10^7,n_i \mid (p_i - 1)。