F. Fire Kings
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After a long ACPC contest, Mouf could finally buy a new Yu-Gi-Oh structure deck "Fire Kings". He was amazed by how strong this deck is, and now he is ready to duel with Jack Atlas, The Crimson King.

However, during the duel, Mouf found a little problem. Calculating the damage he inflicted on Jack is very complicated as Fire Kings monsters are burning the field! Mouf has $$$n$$$ monsters on the field, and each of them has the following five parameters:

Level $$$l$$$, strength $$$s$$$, developing rate $$$x$$$, damage suppression $$$ds$$$, and $$$t$$$, the number of turns it will remain on the field before it will be destroyed.

Every monster will do the following until the end of the $$$t_{th}$$$ turn, respectively:

  • It attacks Jack, causing $$$l \cdot s$$$ damage to him. But the attack will not disappear; instead, it will last until the $$$t_{th}$$$ turn and continue burning Jack every turn by $$$\left (\frac{l \cdot s}{ds^{tt}} \right)$$$, where $$$tt$$$ is the number of turns that have passed since the attack time.

  • The level of the monster will increase by $$$x$$$.

It took Mouf a few minutes to calculate damage fast, and now he is challenging you -yes, you bot! For every monster given in the input, output the total damage it causes during all $$$t$$$ turns modulo $$$10^9+7$$$.

Input

The first line of the input contains one integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^4)$$$ — the number of monsters Mouf has on the field.

Then next $$$n$$$ lines follows, each of them contains five integers $$$l$$$, $$$s$$$, $$$x$$$, $$$ds$$$, $$$t$$$ $$$(1 \le l, s, x, ds, t \le 10^9)$$$.

Output

Print $$$n$$$ lines, the $$$i$$$-th line contains one integer, the total damage the $$$i$$$-th monster causes to Jack Atlas, modulo $$$10^9+7$$$.

Examples
Input
1
1 8 2 2 3
Output
90
Input
3
5 4 6 9 8
2 9 5 8 3
6 9 8 1 9
Output
149564498
656250204
11070
Note

In the first test case, Mouf has a monster with these parameters: $$$l=1, s=8, x=2, ds=2, t=3$$$. Then the following will happen:

  • First turn: the monster will cause $$$1 \cdot 8 = 8$$$ damage and $$$\frac{8}{2} = 4$$$ and $$$\frac{8}{4} = 2$$$ damage on the second and third turn, respectively. After that, its level will increase by 2 and become 3.
  • Second turn: the monster will cause $$$3 \cdot 8 = 24$$$ damage and $$$\frac{24}{2} = 12$$$ damage on the third turn. After that, its level will increase and become $$$5$$$.
  • Third turn: the monster will cause $$$5 \cdot 8 = 40$$$ damage. After that, its level will increase and become $$$7$$$.

During the end of the third turn, the monster will be destroyed, and the total damage it causes is $$$8 + 4 + 2 + 24 + 12 + 40 = 90$$$.