408042: GYM102966 F Fitness Baker

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?

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.

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$$$.

1
5
3

16
61000
4680