CRDS - Cards

第一行为N组 接下来N行 每行一个询问  具体图片 最下面的不需要底部摆卡片 像这样摆放M层，需要多少卡片 附：由于数会很大,输出时应%1,000,007.

Maricruz have a lot of cards, she always uses her cards to build pyramids as shown in the following image:  A pyramid card of 3 levels. She always wonder how many cards does she need to make a pyramid card of **N** levels. Your task is to answer that question.

The first line of the input contains an integer 1 <= **T** <= 1,000. Each of the following **T** lines will have an integer 1 <= **N** <= 1,000,000.

For each case, output a single line consisting of the number of cards needed to build a pyramid card of level **N** modulo 1,000,007.

Example
2
3
7

Example
15
77