After King Midas was granted his wish of having everything he touched turn into gold, he was delighted. However, he soon realized that this prevented him from eating and drinking. After this dawned upon him, Midas was so struck that he had to cope. He decides to take a walk on the beach, but he accidentally touches the ocean, contaminating it with gold. It turns out, the population of amoebas living in the ocean had their reproductive cycle disrupted! In fact, the amoebas have become golden amoebas, and they now produce gold particles.

After Midas touched the ocean, there were ~A~ golden amoebas and ~G~ gold particles in the ocean. Every year, ~P~ gold particles are produced from every golden amoeba, and then the population of golden amoebas increases by ~X~ times. Not only that, every gold particle turns into ~Y~ golden amoebas after being in the ocean for a year.

The golden amoeba population will continue to evolve after King Midas touches the ocean. Can you tell King Midas how many golden amoebas and gold particles are in the ocean, modulo ~10^9 + 7~, if he cries for ~T~ years? To really learn his lesson, you need to answer ~Q~ queries.

Input Specification

The first line will contain ~Q~ ~(1 \le Q \le 10^5)~, the number of queries you need to answer until King Midas learns his lesson.

The second line will contain the integers, ~A~ ~(0 \le X \le 10^9)~, ~G~ ~(0 \le G \le 10^9)~, the number of amoebas and gold particles in the ocean before King Midas touches the ocean.

The third line will contain 3 space-separated integers, ~P~ ~(0 \le P \le 10^9)~, ~X~ ~(0 \le X \le 10^9)~, and ~Y~ ~(0 \le Y \le 10^9)~, the number of gold particles produced by each golden amoeba, the factor that the golden amoeba population grows, and the number of golden amoebas produced by each gold particle after being in the ocean for a year.

The next ~Q~ lines will contain an integer ~T_{i}~ ~(1 \le T_{i} \le 10^{18})~.

Output Specification

On each line, output the population of golden amoebas and gold particles modulo ~10^9 + 7~ separated by a space, after ~T_{i}~ years.

Constraints

Subtask 1 [20%]

~(1 \le T_{i} \le 10^6)~

Subtask 2 [80%]

No additional constraints.

Sample Input

2
100 100
50 50 50
1
2

Sample Output

10000 5000
750000 500000