A regional power company models its distribution network as a tree of n substations, numbered 0 through n-1, with substation 0 being the main plant. Each of the n-1 transformer links connects two substations u and v and reports a step ratio w meaning: one volt measured at substation u corresponds to exactly w volts measured at substation v. The links are listed in no particular order and do not necessarily point away from the plant, but taken together they connect every substation into a single tree with no cycles. Fixing the plant's own reading at exactly 1 volt, determine every substation's reading relative to the plant. Because these ratios can multiply into numbers far too large to store exactly, and because reaching some substations requires walking a link backwards (dividing instead of multiplying), report every reading modulo the prime 1,000,000,007 — where 'dividing' modulo this prime means multiplying by the modular inverse.

Input format

• Line 1: an integer n, the number of substations.
• The next n-1 lines: three integers u v w — a transformer link between substations u and v with step ratio w, meaning one volt at u corresponds to w volts at v.

Output format

• n integers separated by single spaces: the reading of substations 0, 1, ..., n-1 relative to the plant, each taken modulo 1,000,000,007. (Substation 0's own reading is always 1.)

Constraints

• 1 <= n <= 100000
• 1 <= w <= 10^9
• 0 <= u, v <= n-1, and u != v
• The n-1 links form a tree that connects all n substations (no cycles, no repeated links, no self-links).

3
0 1 2
1 2 5

1 2 10

3
1 0 3
1 2 4

1 333333336 333333337