All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Leaf and Limelight Attack
Tag(s):

Dynamic Programming, Easy

Problem
Editorial
Analytics

Limelight is a technique that is used when all four users take place in the cardinal directions. They will then join their strength in the form of four connecting streams above the target area. It will then create a massive ball of lightning powerful enough to incinerate everything within the area of the four users.

enter image description here

The Leaf village is build in the shape of Spiral of integers. Spiral of integers, of an integer $$N$$, is an interesting $$N * N$$ spiral matrix which starts with $$1$$ at the center. For example, for $$N = 4$$, the spiral of integers is

16  15  14  13

5   4   3   12

6   1   2   11

7   8   9   10

Kitane, Nauma, Tōu and Seito are planning to destroy the whole Leaf village. The limelight spot will be the 4 corners of the village. Strength of the attack is equal to the sum of all the elements in the connecting streams as shown in the figure ( sum of diagonal elements of the spiral of integers of $$N$$ ) .

Given the value of $$N$$, you need to compute the strength of the attack (mod $$10^9 + 9$$).

Input:

First line contains an integer $$T$$, denoting the number of testcases.
Each test case consists of a single integer $$N$$.

Output:

For each test case output a single integer denoting the strength of the attack (mod $$10^9 + 9$$).

Constraints:
$$1 \le T \le 10^5$$
$$1 \le N \le 10^7$$

SAMPLE INPUT
2
4
10000000
SAMPLE OUTPUT
56
679604006
Explanation

First test case: Sum of the diagonal elements will be $$16 + 4 + 2 + 10 + 13 + 3 + 1 + 7 = 56.$$

Second test case: Happy Coding :)

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

June Circuits

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications