Innopolis Open 2022-2023. Final round
A. Universal Paperclips
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Universal Paperclips is an incremental game whose goal is to produce paperclips. At your disposal, you have a device that makes paperclips at the click of a button.

For this problem, we'll consider a simplified version of the game with two types of actions:

  1. Click the button. Each click adds a certain amount to the current number of paperclips. This action is denoted by letter "C" ("click").
  2. Upgrade the paperclip-making device. After this action, every subsequence button click will produce one more paperclip. This action is denoted by the letter "U" ("upgrade").

Initially, the player has zero paperclips, and each button click produces one paperclip. An upgrade costs $$$x$$$ paperclips. In all test cases, it's guaranteed that before every upgrade action, the player has at least $$$x$$$ paperclips.

Benny is coding a bot that plays this game. He programmed a fixed sequence of $$$n$$$ actions $$$S$$$, that bot executes cyclically. Every second, the bot makes another action: on the 1st second, the bot executes action $$$S_1$$$, on the 2nd — $$$S_2$$$, ..., on the $$$n$$$-th second it executes $$$S_n$$$, on the $$$n+1$$$-th second — $$$S_1$$$ again, and then the cycle repeats.

How many paperclips will Benny have after his bot runs for $$$t$$$ seconds?

Input

The first line contains three integers $$$n$$$, $$$t$$$ and $$$x$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le t \le 10^9$$$; $$$0 \le x \lt n$$$). The second line contains the string $$$S$$$ of length $$$n$$$, consisting of characters "C" and "U".

Output

Output a single integer — the number of paperclips after $$$t$$$ seconds.

Scoring
SubtaskPointsConstraints
133$$$t \le 10^5$$$
267No additional constraints
Examples
Input
10 15 2
CCCCCUUCCU
Output
25
Input
3 10 0
UUU
Output
0
Input
9 150 1
CCUCCCCUC
Output
2023
Note

Let's go through the first example.

The first five actions produce one paperclip each. Then, the two subsequent upgrades cost two paperclips, so you have only one paperclip left. But, the next two clicks produce three paperclips. The next upgrade costs two paperclips, again. Each one of the last five clicks adds four paperclips.

The final number of paperclips is $$$1 + 1 + 1 + 1 + 1 - 2 - 2 + 3 + 3 - 2 + 4 + 4 + 4 + 4 + 4 = 25$$$.

Statement is not available in English language
C. Sorting Subarrays
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an array of integers. You perform the following action exactly once: choose a non-empty subsegment of the array and order its elements in non-decreasing order.

How many different arrays can you obtain? A subsegment of an array is a collection of several consecutive elements.

Input

The first line contains a single integer $$$n$$$ — the size of the array ($$$1 \le n \le 200\,000$$$).

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ... $$$a_n$$$ — the contents of the array ($$$1 \le a_i \le 10^9$$$).

Output

Output a single integer — the number of different arrays you can obtain by sorting a subsegment once.

Scoring
SubtaskPointsConstraints
113$$$n \le 50$$$
226$$$n \le 3\,000$$$
322$$$1 \le a_i \le 2$$$
439No additional constraints
Examples
Input
7
3 1 4 1 5 9 2
Output
8
Input
4
1 2 3 4
Output
1
Note

Listed below are all eight achievable arrays in the first example. Square brackets indicate the sorted subsegment.

  1. $$$[3], 1, 4, 1, 5, 9, 2 \rightarrow 3, 1, 4, 1, 5, 9, 2$$$
  2. $$$[3, 1], 4, 1, 5, 9, 2 \rightarrow 1, 3, 4, 1, 5, 9, 2$$$
  3. $$$[3, 1, 4, 1], 5, 9, 2 \rightarrow 1, 1, 3, 4, 5, 9, 2$$$
  4. $$$[3, 1, 4, 1, 5, 9, 2] \rightarrow 1, 1, 2, 3, 4, 5, 9$$$
  5. $$$3, [1, 4, 1], 5, 9, 2 \rightarrow 3, 1, 1, 4, 5, 9, 2$$$
  6. $$$3, [1, 4, 1, 5, 9, 2] \rightarrow 3, 1, 1, 2, 4, 5, 9$$$
  7. $$$3, 1, 4, [1, 5, 9, 2] \rightarrow 3, 1, 4, 1, 2, 5, 9$$$
  8. $$$3, 1, 4, 1, 5, [9, 2] \rightarrow 3, 1, 4, 1, 5, 2, 9$$$

D. RestORe
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Consider a sequence of non-negative integers from $$$L$$$ to $$$R$$$ inclusive. Split this sequence into $$$n$$$ non-empty segments and calculate the bitwise "OR" of all numbers in each segment. Denote the result for the $$$i$$$-th segment as $$$f_i$$$.

You need to solve the inverse problem: given $$$f_1, f_2, \ldots, f_n$$$, find the number of ways first to select $$$L$$$ and $$$R$$$, and then split all numbers from $$$L$$$ to $$$R$$$ into $$$n$$$ non-empty segments, such that the results of calculating the bitwise "OR" in each segment are equal to $$$f_1, f_2, \ldots, f_n$$$ respectively.

The bitwise "OR" of two non-negative integers is calculated as follows: Write down both arguments in binary, then the $$$i$$$-th bit of the result equals $$$1$$$ iff at least one argument has $$$1$$$ at that place. For example, $$$(17 \mathbin{|} 13) = (10001_2 \mathbin{|} 01101_2) = 11101_2 = 29$$$.

Input

The first line contains integer $$$n$$$ ($$$1 \le n \le 200\,000$$$). The second line contains $$$n$$$ integers $$$f_i$$$ ($$$0 \le f_i \lt 2^{60}$$$).

Output

Output a single integer — the number of ways to choose a sequence of consecutive integers and then split it into $$$n$$$ segments. Because the answer can be huge, print it modulo $$$1\,000\,000\,007$$$.

Scoring
SubtaskPointsConstraints
116$$$n = 1$$$
212$$$n \le 16$$$, $$$0 \le f_ilt; 16$$$
313$$$n \le 256$$$, $$$0 \le f_ilt; 256$$$
418$$$n \le 1024$$$, $$$0 \le f_ilt; 1024$$$
524$$$n \le 30\,000$$$, $$$0 \le f_ilt; 2^{30}$$$
617No additional constraints
Examples
Input
3
0 7 7
Output
4
Input
1
11
Output
6
Input
2
4 6
Output
0
Note

In the first example, there are four ways to split a sequence of consecutive integers into three parts such that their bitwise "OR"s are $$$0$$$, $$$7$$$ and $$$7$$$:

  • $$$[0], [1, 2, 3, 4, 5, 6], [7]$$$: $$$0 = 0$$$; $$$1 \mathbin{|} 2 \mathbin{|} 3 \mathbin{|} 4 \mathbin{|} 5 \mathbin{|} 6 = 7$$$; $$$7 = 7$$$
  • $$$[0], [1, 2, 3, 4, 5], [6, 7]$$$: $$$0 = 0$$$; $$$1 \mathbin{|} 2 \mathbin{|} 3 \mathbin{|} 4 \mathbin{|} 5 = 7$$$; $$$6 \mathbin{|} 7 = 7$$$
  • $$$[0], [1, 2, 3, 4], [5, 6, 7]$$$: $$$0 = 0$$$; $$$1 \mathbin{|} 2 \mathbin{|} 3 \mathbin{|} 4 = 7$$$; $$$5 \mathbin{|} 6 \mathbin{|} 7 = 7$$$
  • $$$[0], [1, 2, 3, 4], [5, 6]$$$: $$$0 = 0$$$; $$$1 \mathbin{|} 2 \mathbin{|} 3 \mathbin{|} 4 = 7$$$; $$$5 \mathbin{|} 6 = 7$$$

E. Non-adjacent Swaps
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a permutation. In one step, you can swap any two adjacent elements if their values differ by more than one.

Consider all permutations that can be obtained using these operations, starting from a given permutation. Define a distance between two permutations as the minimum number of these operations required to transform the first permutation into the second one.

Find the number of permutations that can be obtained and the sum of distances to all those permutations from the starting one.

Input

The first line contains the integer $$$n$$$ ($$$1 \le n \le 100$$$) — the permutation size. The second line contains $$$n$$$ distinct integers $$$a_i$$$ ($$$1 \le a_i \le n$$$) — the starting permutation.

Output

Output two integers, the number of obtainable permutations, and the sum of distances to those permutations. Calculate both numbers modulo $$$1\,000\,000\,007$$$.

Scoring
SubtaskPointsConstraints
115$$$n \le 8$$$
220$$$n \le 15$$$
330$$$n \le 30$$$
420$$$n \le 50$$$
515No additional constraints
Examples
Input
4
3 1 4 2
Output
5 5
Input
5
1 2 3 4 5
Output
1 0
Input
6
5 3 1 2 4 6
Output
61 218
Note

In the first example, you can obtain the following permutations:

  • $$$\lbrack 3, 1, 4, 2 \rbrack$$$, in 0 steps;
  • $$$\lbrack 3, 1, 2, 4 \rbrack$$$, in 1 step;
  • $$$\lbrack 1, 3, 4, 2 \rbrack$$$, in 1 step;
  • $$$\lbrack 3, 4, 1, 2 \rbrack$$$, in 1 step;
  • $$$\lbrack 1, 3, 2, 4 \rbrack$$$, in 2 steps (swap two pairs of elements with values $$$(3, 1)$$$ and $$$(4, 2)$$$).

There are five permutations in total; the sum of distances also equals five.

In the second example, you can't perform any swap, so only one permutation is reachable with a distance of 0.