Summing Subsets#3499
Giriş yap

Summing Subsets

1 saniye
64 megabayt
Çok kolay

Let denote the sum of the elements of a set , and let be the sum of all values over all subsets of the set consisting of the first natural numbers. For example,

F(3) = (1) + (2) + (3) + (1 + 2) + (1 + 3) + (2 + 3) + (1 + 2 + 3) = 24

For a given integer , find the value of the sum F(1) + F(2) + \dots + F(n).

Giriş

The first line contains the number of test cases t~(t \le 1000). Each of the following lines contains one integer n~(1 \le n \le 10^9).

Çıktı

Print lines — one number per line for each corresponding test case. Since the answers may be very large, print them modulo .

Örnekler

Örnek 1

Loading
Loading