410185: GYM103969 E Brownie Brawl

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Brownie Brawltime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

To support local bakeries, you've decided to organize a Brownie Brawl, where competitors face off and try to bake as many brownies as possible in a given time limit!

Before they compete, each baker is interviewed and asked how many brownies they plan on baking:

Baker 1 claims, "I will bake $$$a_1$$$ brownies, and they'll be the best brownies you've ever tasted!"

Similarly, Baker 2 claims, "I plan on baking $$$a_2$$$ brownies, and they're going to be way better than anyone elses."

Baker 3 decides to switch it up, and states: "I'm going to bake $$$a_3$$$ times as many brownies as the previous two bakers, combined. That way, I'll surely win".

This ambitious claim got the crowd roaring, and from then on each baker made a similar claim, to bake $$$a_i$$$ times as many brownies than the previous two bakers combined. As the organizer, you appreciate the enthusiasm, it's also gotten you slightly worried: if everyone bakes as many brownies as they claim, how many brownies will you end up with?

Input

The first line contains a single integer, $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$), the number of bakers. The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), which correspond to each baker's claim.

Output

For each baker, output the number of brownies they claim to bake, modulo $$$10^9+7$$$.

ExampleInput
4
2 3 2 3
Output
2 3 10 39
Note

In the example test case:

Baker 1 and 2 make 2 and 3 brownies, respectively.

Baker 1 and 2 combined bake 5 brownies, so baker 3 makes $$$2 \cdot 5 = 10$$$ brownies.

Baker 2 and 3 combined bake 13 brownies, so baker 4 makes $$$3 \cdot 13 = 39$$$ brownies.

加入题单

上一题 下一题 算法标签: