The Andover Computing Open (TACO) 2023
A. 01 (Easy Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have a binary string $$$S$$$, which is a string only containing 0s and 1s. You can perform the following operation to $$$S$$$ any number of times:

  • Choose a substring $$$01$$$ and delete it from the string.

Output the string left when it's impossible to do any more operations.

Input

A single line with a binary string $$$S$$$ $$$(1\le |S|\le 10^5)$$$.

Output

Output two lines, the length of the final string and the final string.

Examples
Input
00011
Output
1
0
Input
11010101011011111110101
Output
9
111111111

B. Mine Sweeper
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Tianyi is playing a special game of minesweeper. In this game of minesweeper, the player is given a $$$m\times n$$$ grid with an unknown number of mines planted in random positions. Each square $$$(i,j)$$$ where (0,0) is the top left square is labeled with a number $$$a_{(i,j)}$$$ where $$$a_{(i,j)}$$$ denotes the number of mines that are inside the square or share a vertice with the square (In particular, the label of a square can be at most 9).

Tianyi is told that there are no mines on the edges of the minefield. Help Tianyi locate the positions of the random mines.

Input

The first line contains $$$m,n$$$ ($$$3\le m\le 1000$$$, $$$3\le n\le 1000$$$). The following $$$m$$$ lines contain $$$n$$$ integers that denote the label $$$a_{(i,j)}$$$ where $$$0\le i\le m-1$$$ and $$$0\le j\le n-1$$$.

Output

There are $$$k$$$ lines of output where $$$k$$$ is the number of mines for each given minefield. For each line, output $$$i$$$ $$$j$$$ separated by a space where $$$(i,j)$$$ is the position of a mine. Output the positions of the mine in order from top to bottom and left to right.

If there are no mines in the minefield output 0.

Example
Input
6 6
1 1 2 2 2 1
1 1 3 3 3 1
2 2 4 3 3 1
2 3 4 3 2 1
2 3 3 2 1 1
1 2 2 2 1 1
Output
1 1
1 3
1 4
2 3
3 1
4 1
4 2
4 4

C. Number Machine
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Harry has a strange number machine that has two buttons. The machine has a number $$$x$$$ on its screen. If button A is pressed, the number on the screen changes to $$$3x+2$$$. If button B is pressed, the number on the screen changes to $$$x+1$$$. The initial number on the machine is 1, and Harry wants to change the number to $$$n$$$. Harry is lazy so he wants to press the least number of buttons possible.

What is the minimum number of button presses Harry has to make in order to obtain the number $$$n$$$?

Input

The first line contains the integer $$$n$$$ ($$$1\le n\le 10^{18}$$$).

Output

Output a single integer denoting the minimum number of button presses.

Examples
Input
5
Output
1
Input
20
Output
3

D. Primewords Revisit
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Gunga forgot his computer password again! Darned password manager. He called the campus tech assistants and was able to reset his password. Wahoo!! The first $$$4$$$ digits of his new password are $$$5341$$$ and he noticed that the total of these digits ($$$5+3+4+1=13$$$) is a prime number. His password is $$$n$$$ digits long and each digit is a number from 0 to 9. It didn't take him much time to check all the consecutive 4 digit numbers and add the digits. He was surprised to find that all $$$n-4+1$$$ consecutive quadruplets sum to prime numbers. He gave a name to this type of password: prime-words.

He starts to wonder how many possible $$$n$$$ digit passwords are prime-words. For example, when $$$n=5$$$, $$$53419$$$ is a prime-word since $$$5+3+4+1=13,3+4+1+9=17$$$ are both prime. Each digit can be $$$0-9$$$. Help Gunga find the number of $$$n$$$ digit prime-words (the total of each consecutive 4 digits is a prime number). Since the number can be large, output the answer $$$\pmod{10^9+7}$$$.

Input

The first line contains a single integer $$$n$$$ $$$(1\le n\le 5\times 10^4)$$$ - the number of digits.

Output

A single integer, the number of $$$n$$$ digit prime-words $$$\pmod{10^9+7}$$$.

Examples
Input
4
Output
3010
Input
10
Output
3163025

E. Weird Knight
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

We have a weird knight on an infinite 2D-plane. In a move, the weird $$$(p,q)$$$-knight on $$$(x,y)$$$ can move to $$$(x+p,y+q),(x-p,y+q),(x-p,y+q),(x-p,y-q),(x+q,y+p),(x+q,y-p),(x-q,y+p),(x-q,y-p)$$$.

For example, the knight in a normal chess game is a $$$(2,1)$$$-knight by our definition.

Is it possible for the $$$(p,q)$$$-knight to move from $$$(0,0)$$$ to $$$(x,y)$$$ ?

Input

The first line contains a single integer $$$T$$$ $$$(1\le T\le 10^4)$$$— the number of test cases. The description of test cases follows. The first line of each test case contains 4 integers $$$p,q,x,y$$$ $$$(-10^{9}\le p,q,x,y\le 10^9)$$$.

Output

For each test case, print "Yes" if it's possible for the $$$(p,q)$$$-knight to move from $$$(0,0)$$$ to $$$(x,y)$$$. Otherwise, print "No".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Examples
Input
1
2 3 0 2
Output
YES
Input
1
1 3 5 10
Output
NO

F. Double-Ended Queue
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Gunga just learned what a double-ended queue is in his data structure class. a double-ended queue (deque) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail).

Now, he is playing with his own double-ended queue. He has an empty double-ended queue $$$B$$$ and an array of integers $$$A$$$. In the $$$i$$$-th move, he will add $$$A_i$$$ to one end of $$$B$$$. His goal is to maximize the sum of values from $$$B_L$$$ to $$$B_R$$$, inclusively. $$$B_i$$$ is defined as the $$$i$$$-th element in the deque from the front.

Formally, find the maximum value over all possible $$$B$$$ formed in the end:

$$$$$$\sum_{i=L}^R B_i$$$$$$

Input

The first line contains an integer $$$n,L,R$$$ $$$(1 \leq n \leq 2 \times 10^5,1\le L\le R\le n)$$$ – the number of integers and Gunga's favorite interval.

The second line contains $$$n$$$ space-separated integers $$$A_1, A_2, \ldots, A_n$$$ $$$(-10^9 \leq A_i \leq 10^9)$$$.

Output

Output the maximum sum from $$$B_L$$$ to $$$B_R$$$.

Examples
Input
5 1 3
1 2 3 4 5
Output
12
Input
10 2 5
3 21 4 2 48 32 12 10 5 9
Output
113

G. Social Network
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ people numbered from $$$1$$$ to $$$n$$$ in a social network. We have $$$m$$$ pieces of information that tell us their connections, in which the $$$i$$$-th one gives us that $$$x_i$$$ are friends with anyone with number $$$y$$$, where $$$L_i\le y\le R_i$$$. Basically, person $$$x_i$$$ is with the range of people from $$$L_i$$$ to $$$R_i$$$.

Now, Harry wants to notify them of an important message. The only way for him to do that is by sending messages to some individuals in the network. If anyone receives a message, he or she will share the message with all his or her friends. Given that friendship is mutual and all pairs of friends are included in our information, what is the minimum number of messages Harry needs to send so that everyone in the network receives the message?

Input

The first line contains two integer $$$n,m$$$ $$$(1\le n\le 10^{12},1\le m\le 2\times 10^5)$$$.

The next $$$m$$$ line each contains three integer $$$x_i,L_i,R_i$$$ $$$(1\le x_i\le n,1\le L_i\le R_i\le n)$$$.

Output

Output a single integer, the minimum number of messages Harry needs to send so that everyone in the network receives the message.

Examples
Input
5 3
1 2 2
2 3 3
3 4 4
Output
2
Input
7 2
1 2 4
6 2 3
Output
3
Input
10 4
2 3 6
1 2 3
8 7 9
3 1 5
Output
3

H. 01 (Hard Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have a binary string $$$S$$$, which is a string only containing 0s and 1s. Define $$$f(S)$$$ as the length of the shortest string you get after performing the operation to $$$S$$$:

  • Choose a substring $$$01$$$ and delete it from the string.

Michael is curious about the value of the function $$$f$$$ for some substrings of $$$S$$$. He challenges you to find the answer to some queries of $$$f(S[l,r])$$$. However, he finds that this is not interesting enough, so he might also flip a single bit $$$S_x$$$ of $$$S$$$: changing it from $$$0$$$ to $$$1$$$ or $$$1$$$ to $$$0$$$.

Here, $$$S[l,r]$$$ denotes the substring of $$$S$$$ that starts at the $$$l$$$-th character and ends at the $$$r$$$-th character. For example, if $$$S=abcde$$$, then $$$S[1,3] = abc,S[2,5]=bcde$$$.

Input

The first line contains a single binary string $$$S$$$ $$$(1\le |S|\le 2\times 10^5)$$$.

The second line contains a single integer $$$q$$$ $$$(1\le q\le 2\times 10^5)$$$, the number of operations.

The next $$$q$$$ line each contains an integer $$$k$$$ $$$(k=\{1,2\})$$$, the type of operation.

  • If $$$k=1$$$, the line follows an integer $$$x$$$ $$$(1\le x\le |S|)$$$, the place where Michael flips a bit. If $$$S_x=0$$$, then $$$S_x=1$$$ after this operation. Otherwise, it will be $$$0$$$.
  • If $$$k=2$$$, the line follows two integers $$$l,r$$$ $$$(1\le l\le r\le |S|)$$$, representing the position of Michael's substring of the current query.

Output

For each query with $$$k=2$$$, output a line with the answer $$$f(S[l,r])$$$.

Examples

Input
11001001
4
2 1 3
2 1 8
1 3
2 1 8
Output
3
4
4
Input
1011000110101010010
5
2 1 10
2 1 9
2 1 12
2 3 7
2 4 9
Output
4
3
4
5
2

I. Bad Grades
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Michael received some very bad grades in his classes at Andover. He has taken $$$n$$$ classes. Each class gives Michael a grade in the range from $$$0$$$ to $$$100$$$. Michael doesn't want to fail any classes, so he hacked into the school's computer system to remove all class grades $$$ \lt 60$$$ from his transcript. Given a list of $$$n$$$ numbers, each number is in the range from $$$0$$$ to $$$100$$$, remove all elements $$$ \lt 60$$$ from Michael's list of grades.

Input

The first line contains a number $$$n$$$. $$$1\le n\le 10^5$$$. The next $$$n$$$ lines each contains one of Michael's grades. Each grade is in the range $$$[0, 100]$$$.

Output

Output the new list of grades. You should not change the ordering of Michael's grades.

Example
Input
5
100
90
59
65
40
Output
100
90
65

J. No 7
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Gunga doesn't like the number 7. Given a positive integer $$$x$$$, try to find the maximum integer smaller than $$$x$$$ that does not contain a 7 on any of its digits.

Input

A single integer $$$x$$$ $$$(1\le x\le 10^4)$$$.

Output

The maximum integer smaller than $$$x$$$ that does not contain a 7 on any of its digits.

Examples
Input
8
Output
6
Input
777
Output
699
Note

In the first example, 6 is the maximum integer smaller than 8 that does not contain a 7 on any of its digits.

K. glimmerypond
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Daniel is given a 2D grid representing an $$$n \times m$$$ pond, where each cell can either be filled with water or be empty. The grid is considered glimmery if the number of water-filled cells in any square subgrid of size $$$k \times k$$$ is divisible by 2.

Help Daniel write a function that determines whether a given pond is glimmery or not.

Input

The input parameters are:

$$$n, m, k$$$ each separated by a single space. $$$n$$$ is the number of rows in the pond. $$$m$$$ is the number of columns in the pond. Both $$$n, m$$$ satisfy $$$1\le n, m\le 100$$$. $$$k$$$ satisfies $$$1\le k\le \min(n, m)$$$.

This is followed by $$$n$$$ lines. Each line contains $$$m$$$ integers, where 0 denotes an empty cell and 1 represents a water-filled cell.

Output

Ouput "true" if the pond is glimmery, "false" if not.

Example
Input
4 3 2
1 1 0
1 0 0
0 1 0
1 1 1
Output
true

L. Equation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Eric enjoys playing with numbers. One day, he writes $$$0,1,2,\dots,n$$$ on a piece of paper and decides to put $$$+$$$ and $$$-$$$ signs in between them to make the outcome equal to $$$x$$$. Can you help him finish his equation?

Input

A single line that contains two integers $$$n,x$$$ $$$(1\le n\le 100,-\frac{n(n+1)}2\le x\le\frac{n(n+1)}2 )$$$.

Output

If it's possible, output a single line of the final equation. Otherwise, output the string "IMPOSSIBLE" (without quotes).

Examples
Input
3 6
Output
0+1+2+3
Input
4 9
Output
IMPOSSIBLE
Input
15 100
Output
0+1+2+3+4+5+6+7+8+9-10+11+12+13+14+15

M. Tower
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

We have $$$n$$$ towers on a horizontal road. The $$$i$$$-th tower is located at $$$a_i$$$ and has light intensity $$$p_i$$$ unit. However, the effect of this tower's light intensity decreases $$$1$$$ unit for each $$$1$$$ unit distance away. This means that for position $$$x$$$, the light intensity it received from the ith tower will be $$$$$$ \max(0,p_i -|a_i - x|) $$$$$$ For position $$$j$$$, the light intensity it receives is defined as the maximum light intensity of the light intensity from all the towers. Given the position of $$$m$$$ people on the same road, output the light intensity each of them receives.

Input

The first line contains two integers $$$n,m$$$ $$$(1\le n,m\le 2\times 10^5)$$$, representing the number of towers and the number of people.

The next $$$n$$$ lines each contain two integers $$$a_i,p_i$$$ $$$(1\le a_i,p_i\le 10^9)$$$, representing the position and intensity of the $$$i$$$-th tower.

The last line contains $$$m$$$ integers $$$b_1,b_2,\dots,b_m$$$ $$$(1\le b_i\le 10^9)$$$, representing the position of each person.

Output

On the $$$i$$$-th line, output the light intensity received by the $$$i$$$-th person.

Examples
Input
1 5
20 10
20 15 28 10 32
Output
10
5
2
0
0
Input
3 1
1 3
3 3
6 8
2
Output
4

N. Robot
time limit per test
2.5 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Michael's robot is trapped in a maze! The maze is a $$$n\times m$$$ rectangular grid, in which there are some obstacles that the robot cannot pass. Initially, the robot is on $$$(1,1)$$$ of the maze. Fortunately, he can command his robot using a string $$$S$$$ of length $$$K$$$. On the $$$i$$$-th move,

  • If $$$s_i=R$$$, the robot will move from $$$(x,y)$$$ to $$$(x,y+1)$$$
  • If $$$s_i=D$$$, the robot will move from $$$(x,y)$$$ to $$$(x+1,y)$$$

However, his robot fails to receive all his commands! In the string $$$S$$$ received by the robot, if $$$S_i$$$ is a "?", the robot doesn't know the exact command. Find the number of ways the robot can follow the command without hitting an obstacle or leaving the maze. Since the answer can be large, output the answer $$$\pmod{10^9+ 7}$$$.

Input

The first line contains three integers $$$n,m,K$$$ $$$(1\le n,m,K\le 5000)$$$, representing the size of the maze and the length of Michael's command.

For the next $$$n$$$ lines, the $$$i$$$-th line includes a single string $$$A_i$$$, representing the $$$i$$$-th row of the maze. If $$$A_{i,j}=$$$"#", the $$$(i,j)$$$-th block of the maze is an obstacle. Otherwise, $$$A_{i,j}=$$$".".

The last line includes a single string $$$S$$$, the command received by Michael's robot. Each of $$$S$$$ letter is either 'R','D', or '?'.

Output

The number of ways the robot can follow the command without hitting an obstacle or leaving the maze $$$\pmod{10^9 + 7}$$$.

Examples
Input
3 3 3
...
...
...
???
Output
6
Input
4 4 4
.##.
.#..
....
....
D??D
Output
1
Input
9 7 10
.......
..##...
......#
..##..#
.......
.#.....
.....#.
...#...
.....##
?D?DD?R?DD
Output
3
Note

In the first example, the six possible commands that the robot may follow are: $$$DDR,DRD,RDD,RRD,RDR$$$, and $$$DRR$$$.

In the second example, the only possible command that the robot may follow is $$$DDRD$$$. In this way, the robot will follow $$$DDRD$$$. It will follow the path:

$$$$$$(1,1)\to(2,1)\to(3,1)\to(3,2)\to(4,2)$$$$$$

O. Rabbit Jump
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Initially, a rabbit is at $$$(0,0)$$$ on a 2D plane, and it wants to go to $$$(x,y)$$$. It can perform one of the following three jumps:

  • Spend $$$A$$$ carrots to jump to $$$(x+1,y)$$$
  • Spend $$$B$$$ carrots to jump to $$$(x,y+1)$$$
  • Spend $$$C$$$ carrots to jump to $$$(2x,2y)$$$
Output the minimum number of carrots the rabbit needs.
Input

The first line contains an integer $$$T$$$ $$$(1\le T\le 10^4)$$$ - the number of test cases. For the next $$$T$$$ lines, each line contains $$$5$$$ integers $$$x,y,A,B,C$$$ $$$(0\le x,y\le 10^{9},0\le A,B,C\le 10^9)$$$.

Output

For each test case, output an integer, the minimum number of carrots the rabbit needs to jump to $$$(x,y)$$$.

Examples
Input
1
1 1 1 1 1
Output
2
Input
5
3 14 15 92 6
2718 2818 2 8 4
114 514 19 19 810
1024 1024 1 1 1
1249341 12313 1 1 1
Output
324
90
3950
12
34

P. Dungeon
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Free to play, pay to win!
—Anonymous

A knight of level 0 in the dungeon is in trouble! The dungeon can be abstracted as a long path of length $$$D$$$, with the knight initially at position 0. There are two possible events happening in the dungeon:

  1. If he encounters a monster with health $$$h$$$ and his current level is less than $$$h$$$, he has to pay some coins to beat the monster.
  2. If he encounters a shop that sells magic potions that could increase him to level $$$l$$$, he could pay some coins to buy it. However, he won't be able to use the potion if he is already higher than level $$$l$$$.

As a knight, he can never retreat on his way. There are $$$n$$$ monsters and $$$m$$$ shops on his way, the $$$i$$$-th monster is at position $$$a_i$$$, has health $$$h_i$$$, and he needs to pass using $$$f_i$$$ coins if he can't beat it. The $$$i$$$-th shop is at position $$$b_i$$$, sells potions that are able to increase his health level to $$$l_i$$$, and he will need $$$w_i$$$ coins to buy the potion.

What's the minimum money he needs to go through the dungeon?

Input

The first line contains 3 integers $$$D,n,m$$$ $$$(1\le D\le 10^9,1\le n,m\le 10^5)$$$.

The next $$$n$$$ lines each contains 3 integers $$$a_i,h_i,f_i$$$ $$$(1\le a_i\le D,1\le h_i,f_i\le 10^9)$$$.

The next $$$n$$$ lines each contains 3 integers $$$b_i,l_i,w_i$$$ $$$(1\le b_i\le D,1\le l_i,w_i\le 10^9)$$$.

All locations of monsters and shops are distinct.

Output

The minimum number of coins he needs to go through the dungeon.

Examples
Input
10 4 3
1 6 30
3 2 50
5 6 100
8 30 1000
2 5 10
6 30 100
7 30 50
Output
190
Input
8 4 3
2 5 100
4 3 100
5 1 100
7 7 15
1 3 0
6 9 100
8 1 50
Output
115
Note

In the first example, one optimal solution is as follows:

At the first monster, he pays $$$30$$$ coins to pass.

At the first shop, he buys the magic potion with $$$10$$$ coins.

He can beat the second monster with his current health level $$$5$$$.

At the third monster, he pays $$$100$$$ coins to pass.

At the second shop, he buys nothing.

At the third shop, he buys the magic potion with $$$50$$$ coins, recovering to health level $$$30$$$.

He can beat the last monster easily.

The total cost is $$$30 + 10 + 100 + 50=190$$$.

Q. Deque 2 (Easy Version)
time limit per test
2.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The only difference between the easy version and the hard version is the constraint on $$$n$$$.

Gunga just learned what a double-ended queue is in his data structure class. a double-ended queue (deque) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail).

Now, he is playing with his own double-ended queue. He has an empty double-ended queue $$$B$$$ and an array of integers $$$A$$$. In the $$$i$$$-th move, he will add $$$A_i$$$ to one end of $$$B$$$. This time, he wants to find the total sum of the sum of values $$$B_L$$$ to $$$B_R$$$ over all the $$$2^n$$$ possible $$$B$$$ formed. Since the answer can be large, output the answer $$$\pmod{10^9+7}$$$. Two queues are considered different if Gunga's operation on some $$$A_i$$$ is different.

Input

The first line contains an integer $$$n,L,R$$$ $$$(1 \leq n \leq 5 \times 10^3,1\le L\le R\le n)$$$ – the number of integers and Gunga's favorite interval.

The second line contains $$$n$$$ space-separated integers $$$A_1, A_2, \ldots, A_n$$$ $$$(-10^9 \leq A_i \leq 10^9)$$$.

Output

A single integer, the answer $$$\pmod{10^9+7}$$$.

Examples
Input
5 1 5
1 1 1 1 1
Output
160
Input
3 1 2
1 2 3
Output
30
Note

In the first example, no matter which end of the queue Gunga adds the number to, the resulting queue will be $$$[1,1,1,1,1]$$$. The total sum is $$$32\times(1+1+1+1+1)=160$$$.

In the second example, there are $$$8$$$ possible queues $$$B$$$: $$$[1,2,3],[1,2,3],[2,1,3],[2,1,3],[3,2,1],[3,2,1],[3,1,2],[3,1,2]$$$.

The total sum of the sum of $$$B_1$$$ to $$$B_2$$$ is $$$2\times (1+2+2+1+3+2+3+1)=30$$$.

R. Deque 2 (Hard Version)
time limit per test
2.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The only difference between the easy version and the hard version is the constraint on $$$n$$$.

Gunga just learned what a double-ended queue is in his data structure class. a double-ended queue (deque) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail).

Now, he is playing with his own double-ended queue. He has an empty double-ended queue $$$B$$$ and an array of integers $$$A$$$. In the $$$i$$$-th move, he will add $$$A_i$$$ to one end of $$$B$$$. This time, he wants to find the total sum of the sum of values $$$B_L$$$ to $$$B_R$$$ over all the $$$2^n$$$ possible $$$B$$$ formed. Since the answer can be large, output the answer $$$\pmod{10^9+7}$$$. Two queues are considered different if Gunga's operation on some $$$A_i$$$ is different.

Input

The first line contains an integer $$$n,L,R$$$ $$$(1 \leq n \leq 5 \times 10^5,1\le L\le R\le n)$$$ – the number of integers and Gunga's favorite interval.

The second line contains $$$n$$$ space-separated integers $$$A_1, A_2, \ldots, A_n$$$ $$$(-10^9 \leq A_i \leq 10^9)$$$.

Output

A single integer, the answer $$$\pmod{10^9+7}$$$.

Examples
Input
5 1 5
1 1 1 1 1
Output
160
Input
3 1 2
1 2 3
Output
30
Note

In the first example, no matter which end of the queue Gunga adds the number to, the resulting queue will be $$$[1,1,1,1,1]$$$. The total sum is $$$32\times(1+1+1+1+1)=160$$$.

In the second example, there are $$$8$$$ possible queues $$$B$$$: $$$[1,2,3],[1,2,3],[2,1,3],[2,1,3],[3,2,1],[3,2,1],[3,1,2],[3,1,2]$$$.

The total sum of the sum of $$$B_1$$$ to $$$B_2$$$ is $$$2\times (1+2+2+1+3+2+3+1)=30$$$.