LCM equation

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian
Chef is exploring a new mathematical problem, which can be stated as follows:
where [x] means greatest integer which doesn't exceed x.
Chef wants you to answer some questions for a given pair of integers N, K:
What is the least common multiple of F(N, 1), F(N, 2), ... , F(N, K) modulo 10^{9} + 7.
Chef is not willing to give you all queries at once. Instead, he gives you the first query and suggests you generate all the following queries in this way:
N_{i} = 1 + (A * Answer_{i1} + C_{i}) mod M ,
K_{i} = 1 + (B * Answer_{i1} + D_{i}) mod N_{i},
where Answer_{i} is the answer for the i^{th} query.
Input
The first line of input contains an integer T denoting the number of questions Chef wants to ask you.
Second line contains two spaceseparated integers N_{1}, K_{1}.
Third line contains three spaceseparated integers A, B, and M, described in the statement.
Next line contains T1 spaceseparated integers: C_{2}, C_{3}, ... , C_{T}
Next line contains T1 spaceseparated integers: D_{2}, D_{3}, ... , D_{T}
Output
For each test case, output a single integer — the answer for the given query.
Constraints and Subtasks
 1 ≤ T ≤ 10^{6}
 0 ≤ A, B, C_{i}, D_{i} < M ≤ 10^{5}
 1 ≤ K_{1} ≤ N_{1}< M
Subtask1:(10 points)
 1 ≤ M ≤ 10
 Time Limit is 1 second
Subtask2: (20 points)
 1 ≤ T ≤ 10^{2}
 1 ≤ M ≤ 10^{3}
 Time Limit is 1 second
Subtask3: (30 points)
 A = B = 0
 Time Limit is 4 seconds
Subtask4: (40 points)
 No additional constraints
 Time Limit is 4 seconds
Example
Input: 3 2 1 0 0 3 2 2 0 1 Output: 2 3 6
Input: 4 5 2 2 3 6 4 2 3 2 4 2 Output: 20 6 6 4Explanation
Example case 1. F(2,1) = F(2,2) = 2, F(3,1) = 3, F(3,2) = 6, F(3,3) = 3 1st query  (2,1). Answer = 2. 2nd query  (3,1). Answer = 3 3rd query  (3,2). Answer = 6
Example case 2. F(4,1) = 4, F(5,2) = 20 1st query  (5,2). Answer = lcm(F(5,1), F(5,2)) = lcm(5,20) = 20 2nd query  (1 + (20 * 2 + 4) mod 6, 1 + (20 * 3 + 2) mod n) = (3, 3). Answer = lcm(F(3,1), F(3,2), F(3,3)) = lcm(3,6,3) = 6 3rd query  (1 + (6*2 + 2) mod 6, 1 + (6*3 + 4) mod n) = (3,2). Answer = lcm(F(3,1), F(3,2)) = 6 4th query  (1 + (6*2 + 3) mod 6, 1 + (6*3 + 2) mod n) = (4,1). Answer = lcm(F(4,1)) = 4
Author:  kaizer 
Editorial  http://discuss.codechef.com/problems/LOTERY 
Tags  kaizer, lcm, mediumhard, oct15, segmenttree 
Date Added:  5092015 
Time Limit:  1  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions