Krosh has an array of $$$n$$$ integers. Help him to calculate the following value: $$$\sum\limits_{i=1}^n \sum\limits_{j=i+1}^n |a_i - a_j| * (a_i + a_j)$$$. Output it modulo $$$10^9+7$$$.

Krosh has an array of $$$n$$$ non-negative integers. He determines the beauty of array in the following way. He picks a number $$$1 \le k \le n$$$ and some sequence $$$b$$$ of $$$k$$$ different integers $$$1 \le b_i \le n$$$. Then he determines the value of this sequence $$$V(b)$$$ as sum of elements of an array $$$a$$$ on the corresponding positions from array $$$b$$$: $$$V(b) = \sum \limits_{i = 1}^k a_{b_i}$$$. Then the beauty of an array $$$a$$$ equals to bitwise xor of all the values $$$V(b)$$$ over all possible sequences $$$b$$$ which can be obtained in the way described above(pick $$$k$$$ and $$$k$$$ different numbers from $$$1$$$ to $$$n$$$). Help Krosh to determine the beauty of an array $$$a$$$.

You are given an array of $$$n$$$ positive integers. You should determine is it possible to reorder it's elements in such a way that condition $$$a_1 \lt a_2 \gt a_3 \lt a_4 \gt a_5... $$$ is true. In other words, first element should be strictly less than the second, the second element should be strictly greater than the third etc. If such order exists output $$$n$$$ numbers – the resulting array. If no, just output $$$-1$$$. If there are more than one correct order output any of correct arrays.

Krosh has a homework: calculate the sum of the following series: $$$\sum\limits_{n = 1}^{\infty} \frac{n^k}{2^n}$$$, where $$$k$$$ is given. Help him to calculate it. It's guaranteed that the answer is integer. Output it modulo $$$10^9+7$$$.

Krosh has been learning probability theory and came up with the following problem: consider an array of $$$n$$$ natural numbers from $$$1$$$ to $$$x$$$ and natural number $$$k$$$. Then $$$k$$$ steps follow, on each step we take current array and simultaneously insert a random number from $$$1$$$ to $$$x$$$ between every pair of adjacent numbers, these numbers are chosen equiprobably and independently on each step and in each step. Krosh is interested what is expected number of segments consisting of the equal numbers after $$$k$$$ steps of the algorithm? For example, if $$$a = [1, 2, 4, 1, 1, 5, 5, 6]$$$, $$$x = 6$$$, then number of segments is $$$6$$$. After one step we can obtain the array: $$$[1, 5, 2, 2, 4, 3, 1, 1, 1, 1, 5, 6, 5, 2, 6]$$$ with $$$11$$$ segments.

Krosh has two numbers $$$n$$$ and $$$m$$$. He calls an array consisting of $$$k$$$ elements good, if any two adjacent numbers differ only by one, so for any $$$1 \le i \le k - 1$$$ $$$|a_i - a_{i + 1}| = 1$$$. Array of length $$$1$$$ is always good. Help Krosh to calculate number of arrays of size $$$m$$$ elements consisting of natural numbers from $$$1$$$ to $$$n$$$ such that every number from $$$1$$$ to $$$n$$$ appears at least once in this array. Answer can be large so output it modulo $$$10^9+7$$$. Two arrays are different if there exists a position in which two elements differ.

Krosh calls an array of length $$$n$$$ interesting if it consists of numbers from $$$0$$$ to $$$9$$$ and sum of array is divisible by $$$3$$$. Help him to count number of interesting arrays of length $$$n$$$.

Krosh has three integers $$$n$$$, $$$m$$$, $$$k$$$. Help him to calculate number of arrays with following properties:

1. Number of elements in the array is $$$n$$$

2. Every element of the array is integer between $$$1$$$ and $$$m$$$

3. Sum of the array is divisible by $$$k$$$.

Output amount of these arrays modulo $$$10^9+7$$$.

Krosh has the array $$$a$$$ of $$$n$$$ non-negative integers. Help him to calculate the following value:

$$$\sum\limits_{l = 1}^n \sum\limits_{r = l}^n (a(l) $$$ $$$^$$$ $$$a(l + 1) $$$^$$$ $$$... $$$^$$$ $$$a(r)) * max(a(l), a(l + 1), ..., a(r))$$$ (^ - bitwise XOR).

Output the answer modulo $$$10^9+7$$$.

Krosh has an array of $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ and some number $$$m$$$. He determines beauty $$$F$$$ of the sequence $$$a_1, a_2, ..., a_n$$$ in the following way: $$$F(A) = a_1 $$$ $$$mod$$$ $$$m$$$ $$$+ a_2 ^ 2$$$ $$$mod$$$ $$$m$$$ $$$+ a_3 ^ 3$$$ $$$mod$$$ $$$m$$$ + ... + $$$a_n ^ n$$$ $$$mod$$$ $$$m$$$(number above is the power) where $$$x$$$ $$$mod$$$ $$$m$$$ is reminder from division of $$$x$$$ to $$$m$$$. Krosh wants to reorder elements in his array in a way that maximizes it's beauty. Help him to determine maximum possible beauty of the array.