apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an integer $$$n$$$.

Find any pair of integers $$$(x,y)$$$ ($$$1\leq x,y\leq n$$$) such that $$$x^y\cdot y+y^x\cdot x = n$$$.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 10^4$$$) — the number of test cases.

Each test case contains one line with a single integer $$$n$$$ ($$$1\leq n\leq 10^9$$$).

## Output Format
For each test case, if possible, print two integers $$$x$$$ and $$$y$$$ ($$$1\leq x,y\leq n$$$). If there are multiple answers, print any.

Otherwise, print $$$-1$$$.

## Examples
```input
5
3
7
42
31250
20732790
```
```output
-1
-1
2 3
5 5
3 13
```

## Note
In the third test case, $$$2^3 \cdot 3+3^2 \cdot 2 = 42$$$, so $$$(2,3),(3,2)$$$ will be considered as legal solutions.

In the fourth test case, $$$5^5 \cdot 5+5^5 \cdot 5 = 31250$$$, so $$$(5,5)$$$ is a legal solution.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Given an integer $$$n$$$.

Consider all pairs of integer arrays $$$a$$$ and $$$p$$$ of the same length such that $$$n = \prod a_i^{p_i}$$$ (i.e. $$$a_1^{p_1}\cdot a_2^{p_2}\cdot\ldots$$$) ($$$a_i>1;p_i>0$$$) and $$$a_i$$$ is the product of some (possibly one) distinct prime numbers.

For example, for $$$n = 28 = 2^2\cdot 7^1 = 4^1 \cdot 7^1$$$ the array pair $$$a = [2, 7]$$$, $$$p = [2, 1]$$$ is correct, but the pair of arrays $$$a = [4, 7]$$$, $$$p = [1, 1]$$$ is not, because $$$4=2^2$$$ is a product of non-distinct prime numbers.

Your task is to find the maximum value of $$$\sum a_i \cdot p_i$$$ (i.e. $$$a_1\cdot p_1 + a_2\cdot p_2 + \ldots$$$) over all possible pairs of arrays $$$a$$$ and $$$p$$$. Note that you do not need to minimize or maximize the length of the arrays.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each test case contains only one integer $$$n$$$ ($$$2 \le n \le 10^9$$$).

## Output Format
For each test case, print the maximum value of $$$\sum a_i \cdot p_i$$$.

## Examples
```input
7
100
10
864
130056192
1000000000
2
999999018
```
```output
20
10
22
118
90
2
333333009
```

## Note
In the first test case, $$$100 = 10^2$$$ so that $$$a = [10]$$$, $$$p = [2]$$$ when $$$\sum a_i \cdot p_i$$$ hits the maximum value $$$10\cdot 2 = 20$$$. Also, $$$a = [100]$$$, $$$p = [1]$$$ does not work since $$$100$$$ is not made of distinct prime factors.

In the second test case, we can consider $$$10$$$ as $$$10^1$$$, so $$$a = [10]$$$, $$$p = [1]$$$. Notice that when $$$10 = 2^1\cdot 5^1$$$, $$$\sum a_i \cdot p_i = 7$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
RSJ has a sequence $$$a$$$ of $$$n$$$ integers $$$a_1,a_2, \ldots, a_n$$$ and an integer $$$s$$$. For each of $$$a_2,a_3, \ldots, a_{n-1}$$$, he chose a pair of non-negative integers $$$x_i$$$ and $$$y_i$$$ such that $$$x_i+y_i=a_i$$$ and $$$(x_i-s) \cdot (y_i-s) \geq 0$$$.

Now he is interested in the value $$$$$$F = a_1 \cdot x_2+y_2 \cdot x_3+y_3 \cdot x_4 + \ldots + y_{n - 2} \cdot x_{n-1}+y_{n-1} \cdot a_n.$$$$$$

Please help him find the minimum possible value $$$F$$$ he can get by choosing $$$x_i$$$ and $$$y_i$$$ optimally. It can be shown that there is always at least one valid way to choose them.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$, $$$s$$$ ($$$3 \le n \le 2 \cdot 10^5$$$; $$$0 \le s \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^5$$$).

It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print the minimum possible value of $$$F$$$.

## Examples
```input
10
5 0
2 0 1 3 4
5 1
5 3 4 3 5
7 2
7 6 5 4 3 2 1
5 1
1 2 3 4 5
5 2
1 2 3 4 5
4 0
0 1 1 1
5 5
4 3 5 6 4
4 1
0 2 1 0
3 99999
200000 200000 200000
6 8139
7976 129785 12984 78561 173685 15480
```
```output
0
18
32
11
14
0
16
0
40000000000
2700826806
```

## Note
In the first test case, $$$2\cdot 0+0\cdot 1+0\cdot 3+0\cdot 4 = 0$$$.

In the second test case, $$$5\cdot 1+2\cdot 2+2\cdot 2+1\cdot 5 = 18$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
There are $$$n$$$ points $$$1,2,\ldots,n$$$, each point $$$i$$$ has a number $$$a_i$$$ on it. You're playing a game on them. Initially, you are at point $$$1$$$. When you are at point $$$i$$$, take following steps:

- If $$$1\le i\le n$$$, go to $$$i+a_i$$$,
- Otherwise, the game ends.

Before the game begins, you can choose two integers $$$x$$$ and $$$y$$$ satisfying $$$1\le x\le n$$$, $$$-n \le y \le n$$$ and replace $$$a_x$$$ with $$$y$$$ (set $$$a_x := y$$$). Find the number of distinct pairs $$$(x,y)$$$ such that the game that you start after making the change ends in a finite number of steps.

Notice that you do not have to satisfy $$$a_x\not=y$$$.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1\le t\le 10^4)$$$ — the number of test cases.

The first line of each test case contains one integer $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — the number of points.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-n \le a_i \le n$$$) — the numbers on the axis.

It's guaranteed that the sum of $$$n$$$ does not exceed $$$2\cdot 10^5$$$.

## Output Format
For each test case, print a line containing a single integer — the number of distinct pairs $$$(x,y)$$$ with which the game ends.

## Examples
```input
9
1
0
2
-1 0
2
1 -1
2
1 1
3
-1 -2 -1
3
1 -2 -1
4
-1 4 -2 1
5
1 1 1 1 -4
5
1 1 1 1 1
```
```output
2
8
6
7
20
17
34
30
40
```

## Note
In the first test case, the pairs $$$(x,y)$$$ with which the game ends are $$$(1,-1)$$$ and $$$(1,1)$$$, corresponding to the routes $$$1\rightarrow 0$$$ and $$$1\rightarrow 2$$$. Note that $$$(1,2)$$$ is invalid since when $$$n=1$$$, $$$y=2$$$ violates $$$-n\le y\le n$$$. $$$(1,0)$$$ is also invalid since you will go from $$$1$$$ to $$$1$$$ forever.

In the second test case, the pairs are $$$(1,-2),(1,-1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)$$$.

In the fourth test case, the pairs are $$$(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,1),(2,2)$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
There is an array $$$a$$$ consisting of non-negative integers. You can choose an integer $$$x$$$ and denote $$$b_i=a_i \oplus x$$$ for all $$$1 \le i \le n$$$, where $$$\oplus$$$ denotes the bitwise XOR operation. Is it possible to choose such a number $$$x$$$ that the value of the expression $$$b_1 \oplus b_2 \oplus \ldots \oplus b_n$$$ equals $$$0$$$?

It can be shown that if a valid number $$$x$$$ exists, then there also exists $$$x$$$ such that ($$$0 \le x < 2^8$$$).

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 10^3$$$) — the length of the array $$$a$$$.

The second line of the test case contains $$$n$$$ integers — array $$$a$$$ ($$$0 \le a_i < 2^8$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^3$$$.

## Output Format
For each set test case, print the integer $$$x$$$ ($$$0 \le x < 2^8$$$) if it exists, or $$$-1$$$ otherwise.

## Examples
```input
5
3
1 2 5
3
1 2 3
4
0 1 2 3
4
1 2 2 3
1
1
```
```output
6
0
3
-1
1
```

## Note
In the first test case, after applying the operation with the number $$$6$$$ the array $$$b$$$ becomes $$$[7, 4, 3]$$$, $$$7 \oplus 4 \oplus 3 = 0$$$.

There are other answers in the third test case, such as the number $$$0$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a string $$$s$$$. You can apply this operation to the string exactly once: choose index $$$i$$$ and move character $$$s_i$$$ to the beginning of the string (removing it at the old position). For example, if you apply the operation with index $$$i=4$$$ to the string "abaacd" with numbering from $$$1$$$, you get the string "aabacd". What is the lexicographically minimal$$$^{\dagger}$$$ string you can obtain by this operation?

$$$^{\dagger}$$$A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ of the same length if and only if the following holds:

- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10 ^ 5$$$) — the length of the string.

The second line of each test case contains the string $$$s$$$ of length $$$n$$$, consisting of lowercase English letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10 ^ 5$$$.

## Output Format
For each test case, on a separate line print the lexicographically smallest string that can be obtained after applying the operation to the original string exactly once.

## Examples
```input
4
3
cba
4
acac
5
abbcb
4
aaba
```
```output
acb
aacc
abbcb
aaab
```

## Note
In the first test case, you need to move the last character to the beginning.

In the second case, you need to move the second letter "a".

In the third set you need to apply the operation with $$$i=1$$$, then the string will not change.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a tree (a connected graph without cycles) with $$$n$$$ vertices.

Consider a fixed integer $$$k$$$. Then, the graph $$$G_k$$$ is an undirected graph with $$$n$$$ vertices, where an edge between vertices $$$u$$$ and $$$v$$$ exists if and only if the distance between vertices $$$u$$$ and $$$v$$$ in the given tree is at least $$$k$$$.

For each $$$k$$$ from $$$1$$$ to $$$n$$$, print the number of connected components in the graph $$$G_k$$$.

## Input Format
The first line contains the integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of vertices in the graph.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$), denoting an edge between vertices $$$u$$$ and $$$v$$$ in the tree. It is guaranteed that these edges form a valid tree.

## Output Format
Output $$$n$$$ integers: the number of connected components in the graph $$$G_k$$$ for each $$$k$$$ from $$$1$$$ to $$$n$$$.

## Examples
```input
6
1 2
1 3
2 4
2 5
3 6
```
```output
1 1 2 4 6 6
```
-----
```input
5
1 2
2 3
3 4
3 5
```
```output
1 1 3 5 5
```

## Note
In the first example: If $$$k=1$$$, the graph has an edge between each pair of vertices, so it has one component. If $$$k=4$$$, the graph has only edges $$$4 \leftrightarrow 6$$$ and $$$5 \leftrightarrow 6$$$, so the graph has $$$4$$$ components.

In the second example: when $$$k=1$$$ or $$$k=2$$$ the graph has one component. When $$$k=3$$$ the graph $$$G_k$$$ splits into $$$3$$$ components: one component has vertices $$$1$$$, $$$4$$$ and $$$5$$$, and two more components contain one vertex each. When $$$k=4$$$ or $$$k=5$$$ each vertex is a separate component.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a tree (a connected graph without cycles). Each vertex of the tree contains an integer. Let's define the $$$\mathrm{MAD}$$$ (maximum double) parameter of the tree as the maximum integer that occurs in the vertices of the tree at least $$$2$$$ times. If no number occurs in the tree more than once, then we assume $$$\mathrm{MAD}=0$$$.

Note that if you remove an edge from the tree, it splits into two trees. Let's compute the $$$\mathrm{MAD}$$$ parameters of the two trees and take the maximum of the two values. Let the result be the value of the deleted edge.

For each edge, find its value. Note that we don't actually delete any edges from the tree, the values are to be found independently.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of vertices in the tree.

Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$) — the ends of an edge of the tree. It's guaranteed that the given edges form a valid tree.

The last line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the numbers in the vertices.

## Output Format
For each edge in the input order, print one number — the maximum of the $$$\mathrm{MAD}$$$ parameters of the two trees obtained after removing the given edge from the initial tree.

## Examples
```input
5
1 2
2 3
2 4
1 5
2 1 3 2 1
```
```output
0
2
1
2
```
-----
```input
6
1 2
1 3
1 4
4 5
4 6
1 2 3 1 4 5
```
```output
1
1
0
1
1
```

## Note
In the first example, after removing edge $$$(1, 2)$$$ no number repeats $$$2$$$ times in any of the resulting subtrees, so the answer is $$$\max(0, 0)=0$$$.

After removing edge $$$(2, 3)$$$, in the bigger subtree, $$$1$$$ is repeated twice, and $$$2$$$ is repeated twice, so the $$$\mathrm{MAD}$$$ of this tree is $$$2$$$.

After removing edge $$$(2, 4)$$$, in the bigger subtree, only the number $$$1$$$ is repeated, and in the second subtree, only one number appears, so the answer is $$$1$$$.

In the second example, if edge $$$1 \leftrightarrow 4$$$ is not removed, then one of the subtrees will have two $$$1$$$, so the answer — $$$1$$$. And if edge $$$1 \leftrightarrow 4$$$ is deleted, both subtrees have no repeating values, so the answer is $$$0$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
This is the easy version of the problem. It differs from the hard one only in constraints on $$$n$$$. You can make hacks only if you lock both versions.

Let $$$a_1, a_2, \ldots, a_n$$$ be an array of non-negative integers. Let $$$F(a_1, a_2, \ldots, a_n)$$$ be the sorted in the non-decreasing order array of $$$n - 1$$$ smallest numbers of the form $$$a_i + a_j$$$, where $$$1 \le i < j \le n$$$. In other words, $$$F(a_1, a_2, \ldots, a_n)$$$ is the sorted in the non-decreasing order array of $$$n - 1$$$ smallest sums of all possible pairs of elements of the array $$$a_1, a_2, \ldots, a_n$$$. For example, $$$F(1, 2, 5, 7) = [1 + 2, 1 + 5, 2 + 5] = [3, 6, 7]$$$.

You are given an array of non-negative integers $$$a_1, a_2, \ldots, a_n$$$. Determine the single element of the array $$$\underbrace{F(F(F\ldots F}_{n-1}(a_1, a_2, \ldots, a_n)\ldots))$$$. Since the answer can be quite large, output it modulo $$$10^9+7$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 3000$$$) — the initial length of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the array elements.

## Output Format
Output a single number — the answer modulo $$$10^9 + 7$$$.

## Examples
```input
5
1 2 4 5 6
```
```output
34
```
-----
```input
9
1 1 1 7 7 7 9 9 9
```
```output
256
```
-----
```input
7
1 7 9 2 0 0 9
```
```output
20
```
-----
```input
3
1000000000 1000000000 777
```
```output
1540
```

## Note
In the first test, the array is transformed as follows: $$$[1, 2, 4, 5, 6] \to [3, 5, 6, 6] \to [8, 9, 9] \to [17, 17] \to [34]$$$. The only element of the final array is $$$34$$$.

In the second test, $$$F(a_1, a_2, \ldots, a_n)$$$ is $$$[2, 2, 2, 8, 8, 8, 8, 8]$$$. This array is made up of $$$3$$$ numbers of the form $$$1 + 1$$$ and $$$5$$$ numbers of the form $$$1 + 7$$$.

In the fourth test, the array is transformed as follows: $$$[10^9, 10^9, 777] \to [10^9+777, 10^9+777] \to [2 \cdot 10^9 + 1554]$$$. $$$2 \cdot 10^9 + 1554$$$ modulo $$$10^9+7$$$ equals $$$1540$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
This is the hard version of the problem. It differs from the easy one only in constraints on $$$n$$$. You can make hacks only if you lock both versions.

Let $$$a_1, a_2, \ldots, a_n$$$ be an array of non-negative integers. Let $$$F(a_1, a_2, \ldots, a_n)$$$ be the sorted in the non-decreasing order array of $$$n - 1$$$ smallest numbers of the form $$$a_i + a_j$$$, where $$$1 \le i < j \le n$$$. In other words, $$$F(a_1, a_2, \ldots, a_n)$$$ is the sorted in the non-decreasing order array of $$$n - 1$$$ smallest sums of all possible pairs of elements of the array $$$a_1, a_2, \ldots, a_n$$$. For example, $$$F(1, 2, 5, 7) = [1 + 2, 1 + 5, 2 + 5] = [3, 6, 7]$$$.

You are given an array of non-negative integers $$$a_1, a_2, \ldots, a_n$$$. Determine the single element of the array $$$\underbrace{F(F(F\ldots F}_{n-1}(a_1, a_2, \ldots, a_n)\ldots))$$$. Since the answer can be quite large, output it modulo $$$10^9+7$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the initial length of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the array elements.

## Output Format
Output a single number — the answer modulo $$$10^9 + 7$$$.

## Examples
```input
5
1 2 4 5 6
```
```output
34
```
-----
```input
9
1 1 1 7 7 7 9 9 9
```
```output
256
```
-----
```input
7
1 7 9 2 0 0 9
```
```output
20
```
-----
```input
3
1000000000 1000000000 777
```
```output
1540
```

## Note
In the first test, the array is transformed as follows: $$$[1, 2, 4, 5, 6] \to [3, 5, 6, 6] \to [8, 9, 9] \to [17, 17] \to [34]$$$. The only element of the final array is $$$34$$$.

In the second test, $$$F(a_1, a_2, \ldots, a_n)$$$ is $$$[2, 2, 2, 8, 8, 8, 8, 8]$$$. This array is made up of $$$3$$$ numbers of the form $$$1 + 1$$$ and $$$5$$$ numbers of the form $$$1 + 7$$$.

In the fourth test, the array is transformed as follows: $$$[10^9, 10^9, 777] \to [10^9+777, 10^9+777] \to [2 \cdot 10^9 + 1554]$$$. $$$2 \cdot 10^9 + 1554$$$ modulo $$$10^9+7$$$ equals $$$1540$$$.

Now solve the problem and return the code.