1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Merge Not Sort
Contest: 2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 1900
Tags: constructive algorithms, dp

You are currently researching the Merge Sort algorithm. Merge Sort is a sorting algorithm that is based on the principle of Divide and Conquer. It works by dividing an array into two subarrays of equal length, sorting each subarrays, then merging the sorted subarrays back together to form the final sorted array.

You are particularly interested in the merging routine. Common merge implementation will combine two subarrays by iteratively comparing their first elements, and move the smaller one to a new merged array. More precisely, the merge algorithm can be presented by the following pseudocode.

During your research, you are keen to understand the behaviour of the merge algorithm when arrays $$$A$$$ and $$$B$$$ are not necessarily sorted. For example, if $$$A = [3, 1, 6]$$$ and $$$B = [4, 5, 2]$$$, then $$$\text{Merge}(A, B) = [3, 1, 4, 5, 2, 6]$$$.

To further increase the understanding of the merge algorithm, you decided to work on the following problem. You are given an array $$$C$$$ of length $$$2 \cdot N$$$ such that it is a permutation of $$$1$$$ to $$$2 \cdot N$$$. Construct any two arrays $$$A$$$ and $$$B$$$ of the same length $$$N$$$, such that $$$\text{Merge}(A, B) = C$$$, or determine if it is impossible to do so.

Input format:
The first line consists of an integer $$$N$$$ ($$$1 \leq N \leq 1000$$$).

The following line consists of $$$2 \cdot N$$$ integers $$$C_i$$$. The array $$$C$$$ is a permutation of $$$1$$$ to $$$2 \cdot N$$$.

Output format:
If it is impossible to construct two arrays $$$A$$$ and $$$B$$$ of length $$$N$$$ such that $$$\text{Merge}(A, B) = C$$$, then output -1.

Otherwise, output the arrays $$$A$$$ and $$$B$$$ in two lines. The first line consists of $$$N$$$ integers $$$A_i$$$. The second line consists of $$$N$$$ integers $$$B_i$$$. If there are several possible answers, output any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 1024.0 MB

Note:
Explanation for the sample input/output #1

The solution $$$A = [3, 1, 4]$$$ and $$$B = [5, 2, 6]$$$ is also correct.

Explanation for the sample input/output #2

The solution $$$A = [1, 2, 3, 4]$$$ and $$$B = [5, 6, 7, 8]$$$ is also correct.

Example input:
3
3 1 4 5 2 6

Example output:
3 1 6
4 5 2

Example input:
4
1 2 3 4 5 6 7 8

Example output:
2 3 5 7
1 4 6 8

Editorial:
Maximize The Value
Contest: 2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2100
Tags: data structures, sortings

You are given a one-based array consisting of $$$N$$$ integers: $$$A_1, A_2, \cdots, A_N$$$. Initially, the value of each element is set to $$$0$$$.

There are $$$M$$$ operations (numbered from $$$1$$$ to $$$M$$$). Operation $$$i$$$ is represented by $$$\langle L_i, R_i, X_i \rangle$$$. If operation $$$i$$$ is executed, all elements $$$A_j$$$ for $$$L_i \leq j \leq R_i$$$ will be increased by $$$X_i$$$.

You have to answer $$$Q$$$ independent queries. Each query is represented by $$$\langle K, S, T \rangle$$$ which represents the following task. Choose a range $$$[l, r]$$$ satisfying $$$S \leq l \leq r \leq T$$$, and execute operations $$$l, l + 1, \dots, r$$$. The answer to the query is the maximum value of $$$A_K$$$ after the operations are executed among all possible choices of $$$l$$$ and $$$r$$$.

Input format:
The first line consists of two integers $$$N$$$ $$$M$$$ ($$$1 \leq N, M \leq 100\,000$$$).

Each of the next $$$M$$$ lines consists of three integers $$$L_i$$$ $$$R_i$$$ $$$X_i$$$ ($$$1 \leq L_i \leq R_i \leq N; -100\,000 \leq X_i \leq 100\,000$$$).

The following line consists of an integer $$$Q$$$ ($$$1 \leq Q \leq 100\,000$$$).

Each of the next $$$Q$$$ lines consists of three integers $$$K$$$ $$$S$$$ $$$T$$$ ($$$1 \leq K \leq N; 1 \leq S \leq T \leq M$$$).

Output format:
For each query, output in a single line, an integer which represent the answer of the query.

Constraints:
Time limit: 1.0 s
Memory limit: 1024.0 MB

Note:
Explanation for the sample input/output #1

For query $$$1$$$, one of the solutions is to execute operation $$$4$$$ and $$$5$$$.

For query $$$2$$$, one of the solutions is to execute operation $$$4$$$, $$$5$$$, and $$$6$$$.

For query $$$3$$$, the only solution is to execute operation $$$3$$$.

For query $$$4$$$, the only solution is to execute operation $$$1$$$.

For query $$$6$$$, the only solution is to execute operation $$$2$$$.

Example input:
2 6
1 1 -50
1 2 -20
2 2 -30
1 1 60
1 2 40
2 2 10
5
1 1 6
2 1 6
1 1 3
2 1 3
1 1 2

Example output:
100
50
0
0
-20

Example input:
5 3
1 3 3
2 4 -2
3 5 3
6
1 1 3
2 1 3
3 1 3
3 2 3
2 2 3
2 2 2

Example output:
3
3
4
3
0
-2

Editorial:
Grid Game 2
Contest: 2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2900
Tags: games, number theory

You are playing "Grid Game 2" with your friend. There is a grid with $$$10^9$$$ rows (numbered from $$$1$$$ to $$$10^9$$$) and $$$10^9$$$ columns (numbered from $$$1$$$ to $$$10^9$$$). The cell at row $$$r$$$ and column $$$c$$$ is denoted as $$$(r, c)$$$.

Each cell can have a colour of either black or white. Initially, there are exactly $$$N$$$ black cells (numbered from $$$1$$$ to $$$N$$$). Black cell $$$i$$$ is located at $$$(R_i, C_i)$$$. The rest of the cells are white.

You and your friend will alternately take turn playing on this grid, and you are playing in the first turn. In one turn, a player will choose a black cell $$$(r, c)$$$, then toggle cells $$$(r - x, c - y)$$$ for all $$$0 \leq x, y < \min(r, c)$$$. If a cell is toggled, then the cell becomes black if it was a white cell, and the cell becomes white if it was a black cell.

For example, the following illustration shows how the grid changes after a player chooses a black cell $$$(5, 4)$$$ in their turn.

A player who is unable to play on their turn, i.e. no remaining black cells, loses the game, and the opposing player wins the game. If you and your friend are playing optimally, determine who will win the game.

Input format:
The first line consists of an integer $$$N$$$ ($$$1 \le N \le 200\,000$$$).

Each of the next $$$N$$$ lines consists of two integers $$$R_i$$$ $$$C_i$$$ ($$$1 \leq R_i, C_i \leq 10^9)$$$. For $$$1 \leq i < j \leq N$$$, $$$(R_i, C_i) \neq (R_j, C_j)$$$.

Output format:
Output FIRST if you will win the game, or SECOND otherwise.

Constraints:
Time limit: 1.0 s
Memory limit: 1024.0 MB

Note:
Explanation for the sample input/output #1

You can start your move by choosing $$$(2, 4)$$$, whose effect was demonstrated in the following illustration.

The remaining black cells are $$$(1, 3)$$$ and $$$(1, 4)$$$, each of which will only toggle itself when chosen. Whichever your friend chooses on the next move, the you can choose the remaining black cell.

Explanation for the sample input/output #2

You have only one cell to choose, and will toggle cells $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(2, 1)$$$, and $$$(2, 2)$$$. Your friend and you will alternately choose the remaining black cells with your friend choosing the last black cell.

Example input:
2
2 3
2 4

Example output:
FIRST

Example input:
1
2 2

Example output:
SECOND

Editorial:
Twin Friends
Contest: 2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2200
Tags: combinatorics, dp

You meet two new friends who are twins. The name of the elder twin is $$$A$$$, which consists of $$$N$$$ characters. While the name of the younger twin is $$$B$$$, which consists of $$$M$$$ characters. It is known that $$$N \leq M$$$.

You want to call each of them with a nickname. For the elder twin, you want to pick any permutation of $$$A$$$ as the nickname. For the younger twin, you want to remove exactly $$$M - N$$$ characters from any permutation of $$$B$$$. Denote the nicknames of the elder twin and the younger twin as $$$A'$$$ and $$$B'$$$, respectively.

You want the nicknames to satisfy the following requirement. For each $$$i$$$ that satisfies $$$1 \leq i \leq N$$$, $$$B'_i$$$ must be equal to either $$$A'_i$$$ or the next letter that follows alphabetically after $$$A'_i$$$ (if such a next letter exists).

Determine the number of different pairs of nicknames $$$(A', B')$$$ that satisfy the requirement. Two pairs of nicknames are considered different if at least one of the nicknames are different. As the result might be large, find the answer modulo $$$998\,244\,353$$$.

Input format:
The first line consists of two integers $$$N$$$ $$$M$$$ ($$$1 \leq N \leq M \leq 200\,000$$$).

The second line consists of a string $$$A$$$ of length $$$N$$$.

The third line consists of a string $$$B$$$ of length $$$M$$$.

All strings consist of only upper-case letters.

Output format:
Output a single integer representing number of different pairs $$$(A', B')$$$ that satisfy the requirement, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 1024.0 MB

Note:
Explanation for the sample input/output #1

The $$$9$$$ pairs are:

- (AAM, AAN),
- (AAM, ABN),
- (AAM, BAN),
- (AMA, ANA),
- (AMA, ANB),
- (AMA, BNA),
- (MAA, NAA),
- (MAA, NAB), and
- (MAA, NBA).

Explanation for the sample input/output #2

The $$$120$$$ pairs are the pairs where $$$A'$$$ is a permutation of BINUS and $$$B' = A'$$$.

Example input:
3 4
AMA
ANAB

Example output:
9

Example input:
5 8
BINUS
BINANUSA

Example output:
120

Editorial:
Count BFS Graph
Contest: 2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2100
Tags: combinatorics, dp

You are currently researching a graph traversal algorithm called the Breadth First Search (BFS). Suppose you have an input graph of $$$N$$$ nodes (numbered from $$$1$$$ to $$$N$$$). The graph is represented by an adjacency matrix $$$M$$$, for which node $$$u$$$ can traverse to node $$$v$$$ if $$$M_{u, v}$$$ is $$$1$$$, otherwise it is $$$0$$$. Your algorithm will output the order the nodes are visited in the BFS. The pseudocode of the algorithm is presented as follows.

During your research, you are interested in the following problem. Given an array $$$A$$$ such that $$$A$$$ is a permutation of $$$1$$$ to $$$N$$$ and $$$A_1 = 1$$$. How many simple undirected graph with $$$N$$$ nodes and adjacency matrix $$$M$$$ such that $$$\text{BFS}(M) = A$$$? Since the answer can be very large, calculate the answer modulo $$$998\,244\,353$$$.

A simple graph has no self-loop ($$$M_{i, i} = 0$$$ for $$$1 \leq i \leq N$$$) and there is at most one edge that connects a pair of nodes. In an undirected graph, if node $$$u$$$ is adjacent to node $$$v$$$, then node $$$v$$$ is also adjacent to node $$$u$$$; formally, $$$M_{u, v} = M_{v, u}$$$ for $$$1 \leq u < v \leq N$$$.

Two graphs are considered different if there is an edge that exists in one graph but not the other. In other words, two graphs are considered different if their adjacency matrices are different.

Input format:
The first line consists of an integer $$$N$$$ ($$$2 \leq N \leq 5000$$$).

The second line consists of $$$N$$$ integers $$$A_i$$$. The array $$$A$$$ is a permutation of $$$1$$$ to $$$N$$$ and $$$A_1 = 1$$$.

Output format:
Output an integer representing the number of simple undirected graphs with $$$N$$$ nodes and adjacency matrix $$$M$$$ such that $$$\text{BFS}(M) = A$$$. Since the answer can be very large, output the answer modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 1024.0 MB

Note:
Explanation for the sample input/output #1

The following illustration shows all graphs that satisfy the requirements.

Explanation for the sample input/output #2

The only graph that satisfies the requirements is a graph with two edges: one that connects nodes $$$1$$$ and $$$3$$$, and another one that connects nodes $$$3$$$ and $$$2$$$.

Example input:
3
1 2 3

Example output:
3

Example input:
3
1 3 2

Example output:
1

Editorial:
Deck-Building Game
Contest: 2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2500
Tags: divide and conquer, math

You are playing a deck-building game with your friend. There are $$$N$$$ cards, numbered from $$$1$$$ to $$$N$$$. Card $$$i$$$ has the value of $$$A_i$$$.

You want to build two decks; one for you and one for your friend. A card cannot be inside both decks, and it is allowed to not use all $$$N$$$ cards. It is also allowed for a deck to be empty, i.e. does not contain any cards.

The power of a deck is represented as the bitwise XOR of the value of the cards in the deck. The power of an empty deck is $$$0$$$.

The game is balanced if both decks have the same power.

Determine the number of ways to build two decks such that the game is balanced. Two ways are considered different if one of the decks contains at least one different card. Since the answer can be very large, calculate the answer modulo $$$998\,244\,353$$$.

Input format:
The first line consists of an integer $$$N$$$ ($$$2 \le N \le 100\,000$$$).

The following line consists of $$$N$$$ integers $$$A_i$$$ ($$$1 \le A_i \le 100\,000$$$).

Output format:
Output an integer representing the number of ways to build two decks such that the game is balanced. Output the answer modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 1024.0 MB

Note:
Explanation for the sample input/output #1

Denote $$$S$$$ and $$$T$$$ as the set of cards in your deck and your friend's deck, respectively. There are $$$9$$$ ways to build the decks such that the game is balanced.

- $$$S = \{\}$$$ and $$$T = \{\}$$$. Both decks have the power of $$$0$$$.
- $$$S = \{2, 3, 4\}$$$ and $$$T = \{\}$$$. Both decks have the power of $$$0$$$.
- $$$S = \{\}$$$ and $$$T = \{2, 3, 4\}$$$. Both decks have the power of $$$0$$$.
- $$$S = \{2, 4\}$$$ and $$$T = \{3\}$$$. Both decks have the power of $$$4$$$.
- $$$S = \{3\}$$$ and $$$T = \{2, 4\}$$$. Both decks have the power of $$$4$$$.
- $$$S = \{2, 3\}$$$ and $$$T = \{4\}$$$. Both decks have the power of $$$8$$$.
- $$$S = \{4\}$$$ and $$$T = \{2, 3\}$$$. Both decks have the power of $$$8$$$.
- $$$S = \{3, 4\}$$$ and $$$T = \{2\}$$$. Both decks have the power of $$$12$$$.
- $$$S = \{2\}$$$ and $$$T = \{3, 4\}$$$. Both decks have the power of $$$12$$$.

Explanation for the sample input/output #2

The only way to make the game balanced is to have both decks empty.

Explanation for the sample input/output #3

There are $$$5$$$ ways to build the decks such that the game is balanced.

- $$$S = \{\}$$$ and $$$T = \{\}$$$. Both decks have the power of $$$0$$$.
- $$$S = \{1, 2\}$$$ and $$$T = \{\}$$$. Both decks have the power of $$$0$$$.
- $$$S = \{\}$$$ and $$$T = \{1, 2\}$$$. Both decks have the power of $$$0$$$.
- $$$S = \{1\}$$$ and $$$T = \{2\}$$$. Both decks have the power of $$$1$$$.
- $$$S = \{2\}$$$ and $$$T = \{1\}$$$. Both decks have the power of $$$1$$$.

Example input:
4
16 12 4 8

Example output:
9

Example input:
4
1 2 4 8

Example output:
1

Editorial:
Palindromic Parentheses
Contest: 2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2500
Tags: constructive algorithms

Construct a parentheses sequence consisting of $$$N$$$ characters such that it is balanced and the length of its longest palindromic subsequence (LPS) is exactly $$$K$$$. Determine whether such a construction is possible. If there are several possible sequences, construct any of them.

A parentheses sequence consists of only character ( and ). A parentheses sequence is balanced if each character ( has a corresponding character ) and the pairs of parentheses are properly nested. For example, (), (()), (())(), and ((())()) are balanced. However, )(, ((), and ()) are not balanced.

A sequence is palindromic if it reads the same backwards as forwards. For example, ((, ), ())(, and (()(( are palindromic. However, (), )(, and (()) are not palindromic.

A subsequence can be derived from another sequence by removing zero or more characters without changing the order of the remaining characters. For example, (, ))), ())(, and (())() are subsequence of (())(). However, )(( and ((())) are not subsequence of (())().

The longest palindromic subsequence (LPS) of a sequence is a subsequence with the maximum number of characters, derived from that sequence and it is palindromic. For example, the LPS of sequence (())() is ())(, which can be obtained by removing the second and sixth characters. Therefore, the length of the LPS of (())() is $$$4$$$.

Input format:
Input consists of two integers $$$N$$$ $$$K$$$ ($$$2 \leq N \leq 2000; 1 \leq K \leq N$$$). $$$N$$$ is an even number.

Output format:
If there is no such parentheses sequence such that it is balanced and the length of its LPS is exactly $$$K$$$, then output -1.

Otherwise, output a string of $$$N$$$ characters, representing the parentheses sequence. If there are several possible answers, output any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 1024.0 MB

Note:
Explanation for the sample input/output #2

The LPS of (()()) is either ((( by removing all ) characters, or ))) by removing all ( characters.

The output ((())) also satisfies the requirements.

Explanation for the sample input/output #3

The only possible balanced parentheses sequences are (()) and ()(). The length of the LPS of (()) and ()() are $$$2$$$ and $$$3$$$, respectively.

Explanation for the sample input/output #4

The LPS of ()((())()())() is )())()())(), which can be obtained by removing the first, fourth, and fifth characters.

Example input:
6 4

Example output:
(())()

Example input:
6 3

Example output:
(()())

Editorial:
Triangle Construction
Contest: 2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 1700
Tags: greedy, math

You are given a regular $$$N$$$-sided polygon. Label one arbitrary side as side $$$1$$$, then label the next sides in clockwise order as side $$$2$$$, $$$3$$$, $$$\dots$$$, $$$N$$$. There are $$$A_i$$$ special points on side $$$i$$$. These points are positioned such that side $$$i$$$ is divided into $$$A_i + 1$$$ segments with equal length.

For instance, suppose that you have a regular $$$4$$$-sided polygon, i.e., a square. The following illustration shows how the special points are located within each side when $$$A = [3, 1, 4, 6]$$$. The uppermost side is labelled as side $$$1$$$.

You want to create as many non-degenerate triangles as possible while satisfying the following requirements. Each triangle consists of $$$3$$$ distinct special points (not necessarily from different sides) as its corners. Each special point can only become the corner of at most $$$1$$$ triangle. All triangles must not intersect with each other.

Determine the maximum number of non-degenerate triangles that you can create.

A triangle is non-degenerate if it has a positive area.

Input format:
The first line consists of an integer $$$N$$$ ($$$3 \leq N \leq 200\,000$$$).

The following line consists of $$$N$$$ integers $$$A_i$$$ ($$$1 \leq A_i \leq 2 \cdot 10^9$$$).

Output format:
Output a single integer representing the maximum number of non-degenerate triangles that you can create.

Constraints:
Time limit: 1.0 s
Memory limit: 1024.0 MB

Note:
Explanation for the sample input/output #1

One possible construction which achieves maximum number of non-degenerate triangles can be seen in the following illustration.

Explanation for the sample input/output #2

One possible construction which achieves maximum number of non-degenerate triangles can be seen in the following illustration.

Example input:
4
3 1 4 6

Example output:
4

Example input:
6
1 2 1 2 1 2

Example output:
3

Editorial:
Little Elephant and Bits
Contest: Codeforces Round 157 (Div. 1)
Difficulty rating: 1100
Tags: greedy, math

The Little Elephant has an integer a, written in the binary notation. He wants to write this number on a piece of paper.

To make sure that the number a fits on the piece of paper, the Little Elephant ought to delete exactly one any digit from number a in the binary record. At that a new number appears. It consists of the remaining binary digits, written in the corresponding order (possible, with leading zeroes).

The Little Elephant wants the number he is going to write on the paper to be as large as possible. Help him find the maximum number that he can obtain after deleting exactly one binary digit and print it in the binary notation.

Input format:
The single line contains integer a, written in the binary notation without leading zeroes. This number contains more than 1 and at most 105 digits.

Output format:
In the single line print the number that is written without leading zeroes in the binary notation — the answer to the problem.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample the best strategy is to delete the second digit. That results in number 112 = 310.

In the second sample the best strategy is to delete the third or fourth digits — that results in number 110102 = 2610.

Example input:
101

Example output:
11

Example input:
110010

Example output:
11010

Editorial:
Little Elephant and Elections
Contest: Codeforces Round 157 (Div. 1)
Difficulty rating: 1900
Tags: brute force, combinatorics, dp

There have recently been elections in the zoo. Overall there were 7 main political parties: one of them is the Little Elephant Political Party, 6 other parties have less catchy names.

Political parties find their number in the ballot highly important. Overall there are m possible numbers: 1, 2, ..., m. Each of these 7 parties is going to be assigned in some way to exactly one number, at that, two distinct parties cannot receive the same number.

The Little Elephant Political Party members believe in the lucky digits 4 and 7. They want to evaluate their chances in the elections. For that, they need to find out, how many correct assignments are there, such that the number of lucky digits in the Little Elephant Political Party ballot number is strictly larger than the total number of lucky digits in the ballot numbers of 6 other parties.

Help the Little Elephant Political Party, calculate this number. As the answer can be rather large, print the remainder from dividing it by 1000000007 (109 + 7).

Input format:
A single line contains a single positive integer m (7 ≤ m ≤ 109) — the number of possible numbers in the ballot.

Output format:
In a single line print a single integer — the answer to the problem modulo 1000000007 (109 + 7).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
7

Example output:
0

Example input:
8

Example output:
1440

Editorial:
Little Elephant and LCM
Contest: Codeforces Round 157 (Div. 1)
Difficulty rating: 2000
Tags: binary search, combinatorics, dp, math

The Little Elephant loves the LCM (least common multiple) operation of a non-empty set of positive integers. The result of the LCM operation of k positive integers x1, x2, ..., xk is the minimum positive integer that is divisible by each of numbers xi.

Let's assume that there is a sequence of integers b1, b2, ..., bn. Let's denote their LCMs as lcm(b1, b2, ..., bn) and the maximum of them as max(b1, b2, ..., bn). The Little Elephant considers a sequence b good, if lcm(b1, b2, ..., bn) = max(b1, b2, ..., bn).

The Little Elephant has a sequence of integers a1, a2, ..., an. Help him find the number of good sequences of integers b1, b2, ..., bn, such that for all i (1 ≤ i ≤ n) the following condition fulfills: 1 ≤ bi ≤ ai. As the answer can be rather large, print the remainder from dividing it by 1000000007 (109 + 7).

Input format:
The first line contains a single positive integer n (1 ≤ n ≤ 105) — the number of integers in the sequence a. The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 105) — sequence a.

Output format:
In the single line print a single integer — the answer to the problem modulo 1000000007 (109 + 7).

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
4
1 4 3 2

Example output:
15

Example input:
2
6 3

Example output:
13

Editorial: