Submit | All submissions | Best solutions | Back to list |

## CRDS - Cards |

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.

### Input

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.

### Output

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

Input Example2 3 7Output Example15 77

Added by: | Paulo Costa |

Date: | 2012-01-30 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | C C++ 4.3.2 CPP CPP14 JAVA JS-RHINO JS-MONKEY PYTHON PYTHON3 |

Resource: | UGTO |