問題の背景
ある日、某有名動画配信者であるHちゃんはt時間の間、生放送を実施した。
Hちゃんはこの生配信の視聴者全体の盛り上がり度が気になった。
分かっている情報は視聴者の人数nと盛り上がり度の平均mである。
視聴者全体の盛り上がり度は、一人につきmの盛り上がり度がn人分あるため、n*mで求められる。
しかし、生配信にはゴールデンタイムというものが存在する。ゴールデンタイムとは、その生配信の中でも、特に企画がおもしろく、視聴者の盛り上がり度を稼ぎやすい時間のことである。
このゴールデンタイム中ならば、企画のおもしろさの相乗効果で、なんと視聴者全体の盛り上がり度はn^mにまで跳ね上がるのだ。
ここで問題が発生した。Hちゃんは人気であるが故にnとmの値が大きく、計算しようとしたところ「ふにー！」となってしまったのである。
そこであなたは計算の手伝いをすべく、プログラムを書いて手助けすることとなった。
問題
まず、Hちゃんが生配信を実施した時間の長さtが与えられる。
その後、1時間ごとの視聴者の盛り上がり度に関する情報が与えられるため、視聴者全体の盛り上がり度を計算し、出力してもらいたい。
ただし、計算結果が膨大になることが考えられるので計算結果を1000000007(109+7)で割ったあまりを出力せよ。
また、計算結果の大きさを抑えるため、計算結果だけでなく計算前の値も1000000007(109+7)で割ったあまりとする。
入力
t n0 m0 g0 n1 m1 g1 ・ ・ ・ nt-1 mt-1 gt-1
1行目にHちゃんが生配信を実施した時間 t が与えられる。
続く t 行にわたって、1時間ごとの視聴者の人数 n 、盛り上がり度の平均 m 、ゴールデンタイムかを表す g が空白区切りで入力される。
g が1の時はゴールデンタイムである、0の時はゴールデンタイムでないことを表す。
出力
1時間ごとの視聴者全体の盛り上がり度を1行に出力せよ。
制約
全ての入出力ケースにおいて以下を満たす。
- 1 ≦ t ≦ 10
- 1 ≦ n ≦ 109
- 1 ≦ m ≦ 1013
入出力例
入力例1
3 2 3 0 2 3 1 3 8 1
出力例1
6 8 6561
入力例2
2 2 1000000000 0 2 1000000000 1
出力例2
999999993 140625001
注意点
乗算結果に関しても1000000007で割ったあまりを出力する。