Day Schedule

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
In Chef's world, a single day lasts K hours. There is only one restaurant near Chef's home, and he always eats there. Chef always has his breakfast in the first hour of the day, and it takes him exactly 1 hour to have it. He always has L different dishes for breakfast. Through the rest of the day, Chef has some other smaller meals. Each small meal consists of only a single dish and he finishes eating it in exactly one hour. Each of the remaining hours, he does some activities. There are A different activities that Chef can do (play games, watch TV,... or even sleep). And each of those activities takes exactly one hour.
Chef never eats twice in a row in a day, but he can do the same activity consecutively. Note that, he might eat on the last hour of a day, and then eat in the first hour of the next day, because they are on different days.
Assume that on the first day, the restaurant has D different dishes for Chef to choose from. Each of the next days, a new dish is added to their menu. The Chef wants to plan his schedule for each of the T days, starting from the first day. That is, he wants to decide what dishes he's going to have for breakfast, when and what he'll have for his small meals, and what activities he'll do. Help him calculate sum of the number of different plans he can make for each day. That is, you need to find (the number of different plans possible for day 1) + (the number of different plans possible for day 2) + ... + (the number of different plans possible for day T). Of course, the answer maybe large, so print only the remainder modulo P.
Input
 The first line contains four spaceseparated integers K, A, P, Q, where Q denotes the number of queries.
 Then Q lines follow, each line containing three spaceseparated integers: L, D, T.
Output
Each query, output the answer on a new line.
Constraints
 2 ≤ K ≤ 10^{5}
 1 ≤ A ≤ 10^{9}
 10^{8} + 7 ≤ P ≤ 10^{9} + 7, P is a prime.
 1 ≤ Q ≤ 500
 1 ≤ L ≤ D ≤ D + T  1 ≤ 10^{7}
Subtasks:
 Subtask #1 (5 points): L ≤ D ≤ D + T  1 ≤ 10^{5}
 Subtask #2 (10 points): K = 2
 Subtask #3 (25 points): K ≤ 1000
 Subtask #4 (60 points): Original constrains
Example
Input: 3 2 1000000007 1 1 1 2 Output: 22
Explanations:
There are 3 hours in a day, and 2 activities to choose from. Let the activities be A_{1} and A_{2}. Let the dishes be D_{1} and D_{2}. On Day 1, only D_{1} is available. We will denote a plan for the day by a triplet (X, Y, Z). For example (D_{1}, A_{1}, A_{2}) means that on the first hour, the Chef eats dish D_{1} (which is his breakfast), then the next hour he does the first activity and on the last hour of the day he does the second activity.
All possible plans for the first day are as follows:
 (D_{1}, A_{1}, A_{1})
 (D_{1}, A_{1}, A_{2})
 (D_{1}, A_{1}, D_{1})
 (D_{1}, A_{2}, A_{1})
 (D_{1}, A_{2}, A_{2})
 (D_{1}, A_{2}, D_{1})
So there are total of 6 possible plans for Day 1.
On the second day, the only difference is that D_{2} is also available at the restaurant. All possible plans for the second day are as follows:
 (D_{1}, A_{1}, A_{1})
 (D_{1}, A_{1}, A_{2})
 (D_{1}, A_{1}, D_{1})
 (D_{1}, A_{1}, D_{2})
 (D_{1}, A_{2}, A_{1})
 (D_{1}, A_{2}, A_{2})
 (D_{1}, A_{2}, D_{1})
 (D_{1}, A_{2}, D_{2})
 (D_{2}, A_{1}, A_{1})
 (D_{2}, A_{1}, A_{2})
 (D_{2}, A_{1}, D_{1})
 (D_{2}, A_{1}, D_{2})
 (D_{2}, A_{2}, A_{1})
 (D_{2}, A_{2}, A_{2})
 (D_{2}, A_{2}, D_{1})
 (D_{2}, A_{2}, D_{2})
So, there are 16 possible plans for Day 2. So, the answer is the sum of these two, which is 6 + 16 = 22. Hence that's the output.
Author:  chemthan 
Tags  chemthan, combinatorics, fft, hard, nov17 
Date Added:  23082017 
Time Limit:  6 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 