The Magic Orchard

Jack is a farmer who has fallen on difficult times. After damp weather blighted his vegetable fields, he has been looking for a sturdier alternative than the potatoes and carrots which are prone to rot in the wet ground. However after travelling into town to sell his most recent meagre yield at the marketplace, he has only a few coins left in his pockets. While leaving the marketplace, he is stopped by a strange old man who tells Jack that he is selling magical seeds. The old man promised that during each night the following things would happen:

• Each seed left on the ground in the evening will sprout into 1 tree by morning.
• Each tree will sprout with one branch initially, and will grow 1 additional branch each morning after that.
• Each branch will produce N fruits overnight.
• Each fruit will ripen throughout the day and fall to the ground by evening, rotting way and leaving behind M seeds.

Jack eagerly emptied his pockets and bought S seeds. He rushed home and spread them out into his fields, vowing to not harvest any of the fruit nor seeds for many days in order to maximize his final yield. Jack then went to stay with his cousin for D days before returning later to find his fields filled with an unfathomable amount of trees.

Problem Statement

Input data
First line contains the single value Q, the quantity of test cases.
The following Q lines contain 4 values each: S, N, M, D

Answer
Should be Q space-separated values, corresponding to the number of trees present on day D if S seeds were spread on day 0.
Report all answers modulo 1000000007.

Example

input data:
3
1 0 0 1
5 6 7 8
12 13 14 15

answer:
1 2105 109215470