Snow, riding on her snowmobile, dangerously rushes down a mountain with blinding snow flurrying past her and the wind blowing in her face. Her visibility is limited; all she can see is about 5 meters ahead of her, and everything beyond that is just a white blur.

It's a death wish to ride this fast, especially with such low visibility, but Snow, breathing heavily, steps on the gas, anyways. Currently, it is quarter to midnight on New Year's Eve, and everyone knows what will happen in fifteen minutes: Snowflake Sweets, the most delicious bakery in town, is releasing their new flavor of snow-flavored donuts.

The moment the doors open, customers will flood in in a heartbeat, and the last donut will be sold out within a minute.

Snow passionately cries:

I WILL GET THOSE DONUTS - EVEN IF IT KILLS ME!!

She steps her foot down the whole way and holds her breath as the snowmobile reaches its maximum speed. On her GPS, the estimated arrival time drops from 20 minutes to 10.

Suddenly, the engine groans and spits out a cloud of smoke. The snowmobile decelerates, coming to a complete stop. Snow tries the gas, but it's no good.

She shouts a flurry of curses, then unmounts her snowmobile and props open the hood. At this rate, even if she could fix the engine, there is no way she can make it to the bakery in time.

Her engine consists of ~N~ ~(1 \le N \le 2 \times10^5)~ connector terminals, which are supposed to be connected by ~N-1~ wires. However, upon inspecting the engine, she realizes that every single wire has overloaded and short circuited.

Snow sighs and thinks about what to do. Even if she replaces these regular wires, they will just overload again if she tries to go too fast, so she won't make it on time.

However, she has not given up yet; she still has one last trick up her sleeve. She pulls out a handful of wires from her pockets. Every wire is designated to connect the ~a_i~-th and ~b_i~-th connector terminals.

These wires are not just any regular wires, though - they are hyper-wires! Hyper-wires can increase the speed of the engine exponentially, which should allow Snow to make it on time. Every hyper-wire has a power, ~p_i~ ~(1 \le p_i \le 10^9)~.

To fix her engine, she needs to use some combination of the regular wires (which she can fix and place back into the engine) and her special hyper-wires to connect all ~N~ terminals, such that each terminal can be reached from any other terminal. To save time, she would like to use the minimum number of wires possible to do this.

Besides just connecting all terminals, she also wants the engine's maximum speed to be as high as possible. The snowmobile's engine initially starts with a hyper-charge of ~1~ and a regular charge of ~0~. For every hyper-wire that she uses, the hyper-charge will be multiplied by the power of that hyper-wire, ~p_i~. For every regular wire that she uses, the regular charge will increase by ~1~.

The maximum speed is the final charge, which is equal to the sum of the hyper-charge and the regular charge.

Currently, she has ~M~ hyper-wires in total ~(1 \le M \le 4 \times 10^5)~. Please help her determine the maximum sum of the hyper-charge and the regular charge.

Since this number may be very big, output it modulo ~10^9 + 7~.

Constraints

~1 \le N \le 2 \times 10^5~

~1 \le M \le 4 \times 10^5~

~1 \le p_i \le 10^9~

~1 \le a_i, b_i \le N~

Input Specifications

The first line contains an integer, ~N~.

The following ~N - 1~ lines contain two integers, ~a_i~ and ~b_i~, representing the two terminals that the ~i~-th regular wire connect.

The following line contains an integer, ~M~.

The following ~M~ lines contain three integers, ~a_i~ and ~b_i~ (terminals connected), and ~p_i~, representing the power of the ~i~-th hyper-wire.

Output Specifications

Output one integer, representing the maximum sum of the hyper-charge and the regular charge, modulo ~10^9 + 7~.

Sample Input 1

5
1 2
2 3
2 4
1 5
3
2 3 3
3 4 1
4 2 2

Sample Output 1

8