1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Building an Amusement Park
Contest: COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2300
Tags: binary search, geometry

Mr. Chanek lives in a city represented as a plane. He wants to build an amusement park in the shape of a circle of radius $$$r$$$. The circle must touch the origin (point $$$(0, 0)$$$).

There are $$$n$$$ bird habitats that can be a photo spot for the tourists in the park. The $$$i$$$-th bird habitat is at point $$$p_i = (x_i, y_i)$$$.

Find the minimum radius $$$r$$$ of a park with at least $$$k$$$ bird habitats inside.

A point is considered to be inside the park if and only if the distance between $$$p_i$$$ and the center of the park is less than or equal to the radius of the park. Note that the center and the radius of the park do not need to be integers.

In this problem, it is guaranteed that the given input always has a solution with $$$r \leq 2 \cdot 10^5$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq k \leq n$$$) — the number of bird habitats in the city and the number of bird habitats required to be inside the park.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \leq |x_i|, |y_i| \leq 10^5$$$) — the position of the $$$i$$$-th bird habitat.

Output format:
Output a single real number $$$r$$$ denoting the minimum radius of a park with at least $$$k$$$ bird habitats inside. It is guaranteed that the given input always has a solution with $$$r \leq 2 \cdot 10^5$$$.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-4}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Note:
In the first example, Mr. Chanek can put the center of the park at $$$(-3, -1)$$$ with radius $$$\sqrt{10} \approx 3.162$$$. It can be proven this is the minimum $$$r$$$.

The following illustrates the first example. The blue points represent bird habitats and the red circle represents the amusement park.

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

Example output:
3.1622776589

Example input:
1 1
0 0

Example output:
0.0000000000

Editorial:
Cyclic Sum
Contest: COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 3000
Tags: data structures, fft, number theory

Denote a cyclic sequence of size $$$n$$$ as an array $$$s$$$ such that $$$s_n$$$ is adjacent to $$$s_1$$$. The segment $$$s[r, l]$$$ where $$$l < r$$$ is the concatenation of $$$s[r, n]$$$ and $$$s[1, l]$$$.

You are given an array $$$a$$$ consisting of $$$n$$$ integers. Define $$$b$$$ as the cyclic sequence obtained from concatenating $$$m$$$ copies of $$$a$$$. Note that $$$b$$$ has size $$$n \cdot m$$$.

You are given an integer $$$k$$$ where $$$k = 1$$$ or $$$k$$$ is a prime number. Find the number of different segments in $$$b$$$ where the sum of elements in the segment is divisible by $$$k$$$.

Two segments are considered different if the set of indices of the segments are different. For example, when $$$n = 3$$$ and $$$m = 2$$$, the set of indices for segment $$$s[2, 5]$$$ is $$$\{2, 3, 4, 5\}$$$, and for segment $$$s[5, 2]$$$ is $$$\{5, 6, 1, 2\}$$$. In particular, the segments $$$s[1, 6], s[2,1], \ldots, s[6, 5]$$$ are considered as the same segment.

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

Input format:
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n, m, k \leq 2 \cdot 10^5$$$, $$$k = 1$$$ or $$$k$$$ is a prime number).

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

Output format:
Output an integer denoting the number of different segments in $$$b$$$ where the sum of elements in the segment is divisible by $$$k$$$, modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first example, all valid segments are $$$[1,4]$$$, $$$[2, 3]$$$, $$$[3, 5]$$$, and $$$[4, 2]$$$.

In the second example, one of the valid segments is $$$[1, 5]$$$.

Example input:
5 1 5
1 2 3 4 3

Example output:
4

Example input:
5 1 5
1 2 3 4 5

Example output:
5

Editorial:
Divisible by Twenty-Five
Contest: COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 1800
Tags: brute force, dfs and similar, dp

Mr. Chanek has an integer represented by a string $$$s$$$. Zero or more digits have been erased and are denoted by the character _. There are also zero or more digits marked by the character X, meaning they're the same digit.

Mr. Chanek wants to count the number of possible integer $$$s$$$, where $$$s$$$ is divisible by $$$25$$$. Of course, $$$s$$$ must not contain any leading zero. He can replace the character _ with any digit. He can also replace the character X with any digit, but it must be the same for every character X.

As a note, a leading zero is any 0 digit that comes before the first nonzero digit in a number string in positional notation. For example, 0025 has two leading zeroes. An exception is the integer zero, (0 has no leading zero, but 0000 has three leading zeroes).

Input format:
One line containing the string $$$s$$$ ($$$1 \leq |s| \leq 8$$$). The string $$$s$$$ consists of the characters 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, _, and X.

Output format:
Output an integer denoting the number of possible integer $$$s$$$.

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

Note:
In the first example, the only possible $$$s$$$ is $$$25$$$.

In the second and third example, $$$s \in \{100, 200,300,400,500,600,700,800,900\}$$$.

In the fifth example, all possible $$$s$$$ will have at least one leading zero.

Example input:
25

Example output:
1

Example input:
_00

Example output:
9

Editorial:
Eye-Pleasing City Park Tour
Contest: COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2600
Tags: data structures, trees

There is a city park represented as a tree with $$$n$$$ attractions as its vertices and $$$n - 1$$$ rails as its edges. The $$$i$$$-th attraction has happiness value $$$a_i$$$.

Each rail has a color. It is either black if $$$t_i = 0$$$, or white if $$$t_i = 1$$$. Black trains only operate on a black rail track, and white trains only operate on a white rail track. If you are previously on a black train and want to ride a white train, or you are previously on a white train and want to ride a black train, you need to use $$$1$$$ ticket.

The path of a tour must be a simple path — it must not visit an attraction more than once. You do not need a ticket the first time you board a train. You only have $$$k$$$ tickets, meaning you can only switch train types at most $$$k$$$ times. In particular, you do not need a ticket to go through a path consisting of one rail color.

Define $$$f(u, v)$$$ as the sum of happiness values of the attractions in the tour $$$(u, v)$$$, which is a simple path that starts at the $$$u$$$-th attraction and ends at the $$$v$$$-th attraction. Find the sum of $$$f(u,v)$$$ for all valid tours $$$(u, v)$$$ ($$$1 \leq u \leq v \leq n$$$) that does not need more than $$$k$$$ tickets, modulo $$$10^9 + 7$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq n-1$$$) — the number of attractions in the city park and the number of tickets you have.

The second line contains $$$n$$$ integers $$$a_1, a_2,\ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — the happiness value of each attraction.

The $$$i$$$-th of the next $$$n - 1$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$t_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$0 \leq t_i \leq 1$$$) — an edge between vertices $$$u_i$$$ and $$$v_i$$$ with color $$$t_i$$$. The given edges form a tree.

Output format:
Output an integer denoting the total happiness value for all valid tours $$$(u, v)$$$ ($$$1 \leq u \leq v \leq n$$$), modulo $$$10^9 + 7$$$.

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

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

Example output:
45

Example input:
3 1
1 1 1
1 2 1
3 2 0

Example output:
10

Editorial:
Finding Expected Value
Contest: COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2900
Tags: math

Mr. Chanek opened a letter from his fellow, who is currently studying at Singanesia. Here is what it says.

Define an array $$$b$$$ ($$$0 \leq b_i < k$$$) with $$$n$$$ integers. While there exists a pair $$$(i, j)$$$ such that $$$b_i \ne b_j$$$, do the following operation:

- Randomly pick a number $$$i$$$ satisfying $$$0 \leq i < n$$$. Note that each number $$$i$$$ has a probability of $$$\frac{1}{n}$$$ to be picked.
- Randomly Pick a number $$$j$$$ satisfying $$$0 \leq j < k$$$.
- Change the value of $$$b_i$$$ to $$$j$$$. It is possible for $$$b_i$$$ to be changed to the same value.

Denote $$$f(b)$$$ as the expected number of operations done to $$$b$$$ until all elements of $$$b$$$ are equal.

You are given two integers $$$n$$$ and $$$k$$$, and an array $$$a$$$ ($$$-1 \leq a_i < k$$$) of $$$n$$$ integers.

For every index $$$i$$$ with $$$a_i = -1$$$, replace $$$a_i$$$ with a random number $$$j$$$ satisfying $$$0 \leq j < k$$$. Let $$$c$$$ be the number of occurrences of $$$-1$$$ in $$$a$$$. There are $$$k^c$$$ possibilites of $$$a$$$ after the replacement, each with equal probability of being the final array.

Find the expected value of $$$f(a)$$$ modulo $$$10^9 + 7$$$.

Formally, let $$$M = 10^9 + 7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

After reading the letter, Mr. Chanek gave the task to you. Solve it for the sake of their friendship!

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$2 \leq k \leq 10^9$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \leq a_i < k$$$).

Output format:
Output an integer denoting the expected value of $$$f(a)$$$ modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
2 2
0 1

Example output:
2

Example input:
2 2
0 -1

Example output:
1

Editorial:
GCD Festival
Contest: COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2200
Tags: math, number theory

Mr. Chanek has an array $$$a$$$ of $$$n$$$ integers. The prettiness value of $$$a$$$ is denoted as:

$$$$$$\sum_{i=1}^{n} {\sum_{j=1}^{n} {\gcd(a_i, a_j) \cdot \gcd(i, j)}}$$$$$$

where $$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

In other words, the prettiness value of an array $$$a$$$ is the total sum of $$$\gcd(a_i, a_j) \cdot \gcd(i, j)$$$ for all pairs $$$(i, j)$$$.

Help Mr. Chanek find the prettiness value of $$$a$$$, and output the result modulo $$$10^9 + 7$$$!

Input format:
The first line contains an integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$).

Output format:
Output an integer denoting the prettiness value of $$$a$$$ modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
5
3 6 2 1 4

Example output:
77

Editorial:
Holiday Wall Ornaments
Contest: COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2200
Tags: dp, strings

The Winter holiday will be here soon. Mr. Chanek wants to decorate his house's wall with ornaments. The wall can be represented as a binary string $$$a$$$ of length $$$n$$$. His favorite nephew has another binary string $$$b$$$ of length $$$m$$$ ($$$m \leq n$$$).

Mr. Chanek's nephew loves the non-negative integer $$$k$$$. His nephew wants exactly $$$k$$$ occurrences of $$$b$$$ as substrings in $$$a$$$.

However, Mr. Chanek does not know the value of $$$k$$$. So, for each $$$k$$$ ($$$0 \leq k \leq n - m + 1$$$), find the minimum number of elements in $$$a$$$ that have to be changed such that there are exactly $$$k$$$ occurrences of $$$b$$$ in $$$a$$$.

A string $$$s$$$ occurs exactly $$$k$$$ times in $$$t$$$ if there are exactly $$$k$$$ different pairs $$$(p,q)$$$ such that we can obtain $$$s$$$ by deleting $$$p$$$ characters from the beginning and $$$q$$$ characters from the end of $$$t$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq m \leq n \leq 500$$$) — size of the binary string $$$a$$$ and $$$b$$$ respectively.

The second line contains a binary string $$$a$$$ of length $$$n$$$.

The third line contains a binary string $$$b$$$ of length $$$m$$$.

Output format:
Output $$$n - m + 2$$$ integers — the $$$(k+1)$$$-th integer denotes the minimal number of elements in $$$a$$$ that have to be changed so there are exactly $$$k$$$ occurrences of $$$b$$$ as a substring in $$$a$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
For $$$k = 0$$$, to make the string $$$a$$$ have no occurrence of 101, you can do one character change as follows.

100101011 $$$\rightarrow$$$ 100100011

For $$$k = 1$$$, you can also change a single character.

100101011 $$$\rightarrow$$$ 100001011

For $$$k = 2$$$, no changes are needed.

Example input:
9 3
100101011
101

Example output:
1 1 0 1 6 -1 -1 -1

Editorial:
Illusions of the Desert
Contest: COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2300
Tags: data structures, trees

Chanek Jones is back, helping his long-lost relative Indiana Jones, to find a secret treasure in a maze buried below a desert full of illusions.

The map of the labyrinth forms a tree with $$$n$$$ rooms numbered from $$$1$$$ to $$$n$$$ and $$$n - 1$$$ tunnels connecting them such that it is possible to travel between each pair of rooms through several tunnels.

The $$$i$$$-th room ($$$1 \leq i \leq n$$$) has $$$a_i$$$ illusion rate. To go from the $$$x$$$-th room to the $$$y$$$-th room, there must exist a tunnel between $$$x$$$ and $$$y$$$, and it takes $$$\max(|a_x + a_y|, |a_x - a_y|)$$$ energy. $$$|z|$$$ denotes the absolute value of $$$z$$$.

To prevent grave robbers, the maze can change the illusion rate of any room in it. Chanek and Indiana would ask $$$q$$$ queries.

There are two types of queries to be done:

- $$$1\ u\ c$$$ — The illusion rate of the $$$x$$$-th room is changed to $$$c$$$ ($$$1 \leq u \leq n$$$, $$$0 \leq |c| \leq 10^9$$$).
- $$$2\ u\ v$$$ — Chanek and Indiana ask you the minimum sum of energy needed to take the secret treasure at room $$$v$$$ if they are initially at room $$$u$$$ ($$$1 \leq u, v \leq n$$$).

Help them, so you can get a portion of the treasure!

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq q \leq 10^5$$$) — the number of rooms in the maze and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq |a_i| \leq 10^9$$$) — inital illusion rate of each room.

The $$$i$$$-th of the next $$$n-1$$$ lines contains two integers $$$s_i$$$ and $$$t_i$$$ ($$$1 \leq s_i, t_i \leq n$$$), meaning there is a tunnel connecting $$$s_i$$$-th room and $$$t_i$$$-th room. The given edges form a tree.

The next $$$q$$$ lines contain the query as described. The given queries are valid.

Output format:
For each type $$$2$$$ query, output a line containing an integer — the minimum sum of energy needed for Chanek and Indiana to take the secret treasure.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first query, their movement from the $$$1$$$-st to the $$$2$$$-nd room is as follows.

- $$$1 \rightarrow 5$$$ — takes $$$\max(|10 + 4|, |10 - 4|) = 14$$$ energy.
- $$$5 \rightarrow 6$$$ — takes $$$\max(|4 + (-6)|, |4 - (-6)|) = 10$$$ energy.
- $$$6 \rightarrow 2$$$ — takes $$$\max(|-6 + (-9)|, |-6 - (-9)|) = 15$$$ energy.

In the second query, the illusion rate of the $$$1$$$-st room changes from $$$10$$$ to $$$-3$$$.

In the third query, their movement from the $$$1$$$-st to the $$$2$$$-nd room is as follows.

- $$$1 \rightarrow 5$$$ — takes $$$\max(|-3 + 4|, |-3 - 4|) = 7$$$ energy.
- $$$5 \rightarrow 6$$$ — takes $$$\max(|4 + (-6)|, |4 - (-6)|) = 10$$$ energy.
- $$$6 \rightarrow 2$$$ — takes $$$\max(|-6 + (-9)|, |-6 - (-9)|) = 15$$$ energy.

Now, it takes $$$32$$$ energy.

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

Example output:
39
32
0

Editorial:
Jeopardy of Dropped Balls
Contest: COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 1500
Tags: binary search, brute force, dsu, implementation

Mr. Chanek has a new game called Dropping Balls. Initially, Mr. Chanek has a grid $$$a$$$ of size $$$n \times m$$$

Each cell $$$(x,y)$$$ contains an integer $$$a_{x,y}$$$ denoting the direction of how the ball will move.

- $$$a_{x,y}=1$$$ — the ball will move to the right (the next cell is $$$(x, y + 1)$$$);
- $$$a_{x,y}=2$$$ — the ball will move to the bottom (the next cell is $$$(x + 1, y)$$$);
- $$$a_{x,y}=3$$$ — the ball will move to the left (the next cell is $$$(x, y - 1)$$$).

Every time a ball leaves a cell $$$(x,y)$$$, the integer $$$a_{x,y}$$$ will change to $$$2$$$. Mr. Chanek will drop $$$k$$$ balls sequentially, each starting from the first row, and on the $$$c_1, c_2, \dots, c_k$$$-th ($$$1 \leq c_i \leq m$$$) columns.

Determine in which column each ball will end up in (position of the ball after leaving the grid).

Input format:
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n, m \leq 1000$$$, $$$1 \leq k \leq 10^5$$$) — the size of the grid and the number of balls dropped by Mr. Chanek.

The $$$i$$$-th of the next $$$n$$$ lines contains $$$m$$$ integers $$$a_{i,1},a_{i,2},\ldots,a_{i,m}$$$ ($$$1 \leq a_{i,j} \leq 3$$$). It will satisfy $$$a_{i, 1} \ne 3$$$ and $$$a_{i, m} \ne 1$$$.

The next line contains $$$k$$$ integers $$$c_1, c_2, \ldots, c_k$$$ ($$$1 \leq c_i \leq m$$$) — the balls' column positions dropped by Mr. Chanek sequentially.

Output format:
Output $$$k$$$ integers — the $$$i$$$-th integer denoting the column where the $$$i$$$-th ball will end.

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

Note:
In the first example, the first ball will drop as follows. Note that the cell $$$(1, 1)$$$ will change direction to the bottom direction.

The second and third balls will drop as follows.

All balls will be dropped from the first row and on the $$$c_1, c_2, \dots, c_k$$$-th columns respectively. A ball will stop dropping once it leaves the grid.

Example input:
5 5 3
1 2 3 3 3
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
1 2 1

Example output:
2 2 1

Example input:
1 2 2
1 3
1 2

Example output:
1 2

Editorial:
Knitting Batik
Contest: COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2200
Tags: implementation, math

Mr. Chanek wants to knit a batik, a traditional cloth from Indonesia. The cloth forms a grid $$$a$$$ with size $$$n \times m$$$. There are $$$k$$$ colors, and each cell in the grid can be one of the $$$k$$$ colors.

Define a sub-rectangle as an ordered pair of two cells $$$((x_1, y_1), (x_2, y_2))$$$, denoting the top-left cell and bottom-right cell (inclusively) of a sub-rectangle in $$$a$$$. Two sub-rectangles $$$((x_1, y_1), (x_2, y_2))$$$ and $$$((x_3, y_3), (x_4, y_4))$$$ have the same pattern if and only if the following holds:

- they have the same width ($$$x_2 - x_1 = x_4 - x_3$$$);
- they have the same height ($$$y_2 - y_1 = y_4 - y_3$$$);
- for every pair $$$(i, j)$$$ where $$$0 \leq i \leq x_2 - x_1$$$ and $$$0 \leq j \leq y_2 - y_1$$$, the color of cells $$$(x_1 + i, y_1 + j)$$$ and $$$(x_3 + i, y_3 + j)$$$ are equal.

Count the number of possible batik color combinations, such that the subrectangles $$$((a_x, a_y),(a_x + r - 1, a_y + c - 1))$$$ and $$$((b_x, b_y),(b_x + r - 1, b_y + c - 1))$$$ have the same pattern.

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

Input format:
The first line contains five integers $$$n$$$, $$$m$$$, $$$k$$$, $$$r$$$, and $$$c$$$ ($$$1 \leq n, m \leq 10^9$$$, $$$1 \leq k \leq 10^9$$$, $$$1 \leq r \leq \min(10^6, n)$$$, $$$1 \leq c \leq \min(10^6, m)$$$) — the size of the batik, the number of colors, and size of the sub-rectangle.

The second line contains four integers $$$a_x$$$, $$$a_y$$$, $$$b_x$$$, and $$$b_y$$$ ($$$1 \leq a_x, b_x \leq n$$$, $$$1 \leq a_y, b_y \leq m$$$) — the top-left corners of the first and second sub-rectangle. Both of the sub-rectangles given are inside the grid ($$$1 \leq a_x + r - 1$$$, $$$b_x + r - 1 \leq n$$$, $$$1 \leq a_y + c - 1$$$, $$$b_y + c - 1 \leq m$$$).

Output format:
Output an integer denoting the number of possible batik color combinations modulo $$$10^9 + 7$$$.

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

Note:
The following are all $$$32$$$ possible color combinations in the first example.

Example input:
3 3 2 2 2
1 1 2 2

Example output:
32

Example input:
4 5 170845 2 2
1 4 3 1

Example output:
756680455

Editorial:
Longest Array Deconstruction
Contest: COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2100
Tags: data structures, divide and conquer, dp, sortings

Mr. Chanek gives you a sequence $$$a$$$ indexed from $$$1$$$ to $$$n$$$. Define $$$f(a)$$$ as the number of indices where $$$a_i = i$$$.

You can pick an element from the current sequence and remove it, then concatenate the remaining elements together. For example, if you remove the $$$3$$$-rd element from the sequence $$$[4, 2, 3, 1]$$$, the resulting sequence will be $$$[4, 2, 1]$$$.

You want to remove some elements from $$$a$$$ in order to maximize $$$f(a)$$$, using zero or more operations. Find the largest possible $$$f(a)$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the initial length of the sequence.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2 \cdot 10^5$$$) — the initial sequence $$$a$$$.

Output format:
Output an integer denoting the largest $$$f(a)$$$ that can be obtained by doing zero or more operations.

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

Note:
In the first example, $$$f(A) = 3$$$ by doing the following operations.

$$$[2,1,\textbf{4},2,5,3,7] \rightarrow [\textbf{2},1,2,5,3,7] \rightarrow [1,2,5,3,\textbf{7}] \rightarrow [1,2,\textbf{5},3] \rightarrow [1,2,3]$$$

In the second example, $$$f(A) = 2$$$ and no additional operation is needed.

Example input:
7
2 1 4 2 5 3 7

Example output:
3

Example input:
4
4 2 3 1

Example output:
2

Editorial: