Medium Math > Counting

There are **2*N** nodes in a graph aligned in **2** rows , each row having **N** nodes. The nodes of the first row are sequentially numbered from **1** to **N**. The nodes of the second row are sequentially numbered from **N + 1** to **2*N**. Each node is connected to the node to its left , right , up and down. ![enter image description here][1] The distance between any two adjacent node is **1**. **D(i , j)** denotes the shortest path value between node **i** and node **j**. **Ans** is represented as the following ![enter image description here][2] You have to compute the value of **Ans** or simply all pair shortest path sum. The answer can be huge, so print it modulo **10<sup>9</sup>+7** Input: ------ Input starts with an integer **T (1<= 10<sup>5</sup>)**, denoting the number of test cases. Each case contains an integer **N (1 ≤ N ≤ 10<sup>18</sup> )**. Output: ------- Print the answer for each test case in a single line. Sample Input ------------ 3 1 2 3 Sample Output ------------- 2 16 50 [1]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/9ca38e05-c24c-cfc5-e4a6-08d57eacd894_11a6861cc12b4a729b3a4a474da2adfb_W412xH414.png [2]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/6d72ac7e-5542-ca65-34ce-08d57f2a3d4f_4a419e5fc708427182ccb2c5bed96747_W369xH149.png

Fahim Shahriar Shakkhor