You are given a sequence of $$$n$$$ distinct favourite integers $$$a_1,a_2,a_3,\ldots,a_n$$$ and a number $$$x$$$.

Your task is to calculate the sum of all integers from $$$1$$$ to $$$x$$$, but you should take favourite integers with minus in the sum.

For example, $$$a = [1,4,6], x = 5$$$ the sum is equal to $$$- 1 + 2 + 3 - 4 + 5 = 5$$$, because $$$1$$$, $$$4$$$ are favourite integers. We don't consider $$$6$$$ in our sum as we have to take sum from $$$1$$$ to $$$x$$$ only.

We have a sequence of $$$n$$$ integers and a number $$$x$$$.

Initially $$$a_1 = a_2 = a_3 = \ldots = a_n = x$$$.

In one move, you can choose any index $$$i$$$ if and only if $$$a_i = a_{i+1}$$$ and $$$1 \le i \le n-1$$$ and perform a operation : $$$ a_i = a_i + a_{i+1} $$$ and $$$a_{i+1} = x$$$.

For example - $$$n = 3, x = 5$$$, Initially sequence is $$$a = [5,5,5]$$$,

choose $$$i = 1$$$, array will change to $$$a = [10,5,5]$$$.

choose $$$i = 2$$$, array will change to $$$a = [10,10,5]$$$.

choose $$$i = 1$$$, array will change to $$$a = [20,5,5]$$$.

choose $$$i = 2$$$, array will change to $$$a = [20,10,5]$$$.You cannot choose any index now.

You can perform any number of moves, and any index can be chosen any number of times (including zero). Your task is to find out the maximum possible sum of array we can obtain.

As the answer can be rather large, print the remainder after dividing it by $$$1000000007 (10^9 + 7)$$$.

For the multiset of positive integers $$$a = {(a_1,a_2, \ldots ,a_k)}$$$ define the Greatest Common Divisor (GCD) of $$$a$$$ as:

$$$gcd(a)$$$ is the maximum positive integer $$$x$$$, such that all integers in multiset $$$a$$$ are divisible on $$$x$$$.

For example, $$$gcd({8,12,16})=4$$$.

Singhal has a sequence consisting of $$$n$$$ integers. He wants to find the subarray of $$$(length \gt 1)$$$ whose $$$gcd$$$ is maximum possible. If there exist multiple subarrays then choose the largest in length. Help him to find the maximum gcd he can obtain and length of this subarray.

A subarray is the sequence of consecutive elements of the array.

Singhal has a array of integers $$$a_1,a_2,\ldots,a_n$$$.

Definition of an awesome array —

If $$$K$$$ is the maximum element in the array, then the elements before $$$K$$$ in the array should be in the strictly ascending order and the elements after $$$K$$$ in the array should be in the strictly descending order.

Examples of awesome array are — $$$(1,2,3,1) , (1,2,3) , (3,2,1) , (1,2,1), (2,3,2,1) $$$ , but not $$$ (1,2,2) , (2,2,1) , (1,2,2,3) , (1,3,2,2). $$$

He wants to know that how many distinct awesome arrays he will get after reordering the sequence.

Reorder of array $$$ (1,3,3,4) $$$ can results $$$(1,4,3,3) , (3,4,3,1) ,(4,3,1,3) $$$, but not $$$ (1,3,3,3) , (1,3,3) , (1,3,3,4,4) $$$. You are not allowed to change the value, insert or delete.

Notice that the answer might be large, please output the desired value modulo $$$10^9+7$$$.

Yestarday, Singhal went to a shop. The shop owner is a mathematician and has a unique style of costing the items costumer bought.

If a item has a initial price $$$X (X \ge 2)$$$ , then costumer can bought $$$N$$$ items of this price if $$$X\pmod N = 0$$$ and $$$ 1 \le N \le X-1$$$.

Example - If a item cost $$$X = 10$$$, then costumer can buy these $$$(1,2,5)$$$ numbers of items of this price.

If a item cost $$$X = 12$$$, then costumer can buy these $$$(1,2,3,4,6)$$$ numbers of items.

The shop owner will then calculates the total cost of $$$N$$$ items as -

1) if $$$N$$$ is Prime , cost will be $$$$$$ A + \frac{X}{N} $$$$$$

2) if $$$N$$$ is Composite , cost will be $$$$$$ B + \frac{X}{N} $$$$$$

3) if $$$N$$$ is $$$1$$$ , cost will be $$$$$$ C + \frac{X}{N} $$$$$$

Defn of Prime and Composite number - https://www.mathsisfun.com/prime-composite-number.html.

You know the value of $$$A,B,C$$$ and $$$X$$$. Help him to buy $$$N$$$ number of items of price $$$X$$$ so that cost will be minimum possible.

You don't have to minimize the number of items , only minimize the total cost.

Given a sequence of integers $$$a_1 , a_2 , \ldots , a_n$$$ and a prime number $$$x$$$.

We have a function which takes $$$length$$$ as a parameter and return the maximum possible value of $$$ (a_i\times a_{i+1}\times \cdots \times a_{i+length-1})\pmod x$$$ , where $$$1 \le i \le (n-length+1) $$$.

For example – $$$a = [2,3,4,2] , x = 5 $$$.

For $$$length = 1$$$ , function return $$$\max(2,3,4,2) = 4$$$.

For $$$length = 2$$$ , function return $$$\max((2\times 3)\pmod 5 , (3\times 4)\pmod 5 , (4\times 2)\pmod 5) = \max(1,2,3) = 3$$$.

For $$$length = 3$$$ , function return $$$\max((2\times 3\times 4)\pmod 5 , (3\times 4\times 2)\pmod 5) = \max(4,4) = 4$$$.

For $$$length = 4$$$ , function return $$$\max((2\times 3\times 4\times 2)\pmod 5) = \max(3) = 3$$$.

Your task is to find the smallest length for which this function return maximum possible value.

Singhal has a sequence of integers $$$a_1 , a_2 , \ldots , a_n$$$.

Recall,

A subarray is the sequence of consecutive elements of the array.

$$$ a\pmod n$$$ is the remainder of the Euclidean division of a by n, where a is the dividend and n is the divisor.

A subarray $$$a_i , a_{i+1} , \ldots , a_j $$$ is good if

$$$$$$ (a_i*a_{i+1}*\cdots*a_j)\pmod n = 1 $$$$$$

Formally,

$$$$$$ \Bigl( \prod_{k=i}^j a_k \Bigr)\pmod n = 1$$$$$$

Help him to find if a good subarray is present in his sequence or not. If there are many good subarray tell the smallest possible in length.