408042: GYM102966 F Fitness Baker

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

Description

F. Fitness Bakertime limit per test0.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Baker is living in a new post-modern house. A house of size $$$N$$$ consists of 5 wings arranged in a cross shape, where each wing contains $$$N$$$x$$$N$$$ rooms. For example, a house of size $$$N=$$$ 3 would be arranged as follows:

Each room is connected to the rooms adjacent to it. Baker burns one calorie walking from one room to an adjacent room. Because he is very lazy, Baker will always choose the path that burns the fewest calories. For example, when Baker goes from room $$$X$$$ to room $$$Y$$$ he will burn 5 calories.

Baker wants to know how many calories he would burn walking between every pair of rooms in a given house of size $$$N$$$. Can you help him out?

Input

The input consist of several input lines $$$T$$$ ($$$1 \leq T \leq 200$$$), with one single integer $$$N$$$ ($$$1 \leq N \leq 10^{18}$$$), the size of the house Baker wants to know the amount of calories he might be able to burn if he walks between every pair of rooms.

Output

For each test case in the input print a line with a single number, the amount of calories Baker might burn after walking between every pair of rooms, as this number can be very big print it modulo $$$10^9 + 7$$$.

ExampleInput
1
5
3
Output
16
61000
4680

加入题单

上一题 下一题 算法标签: