1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Permutation Printing
Contest: think-cell Round 1
Difficulty rating: 1000
Tags: brute force, constructive algorithms, math

You are given a positive integer $$$n$$$.

Find a permutation$$$^\dagger$$$ $$$p$$$ of length $$$n$$$ such that there do not exist two distinct indices $$$i$$$ and $$$j$$$ ($$$1 \leq i, j < n$$$; $$$i \neq j$$$) such that $$$p_i$$$ divides $$$p_j$$$ and $$$p_{i+1}$$$ divides $$$p_{j+1}$$$.

Refer to the Notes section for some examples.

Under the constraints of this problem, it can be proven that at least one $$$p$$$ exists.

$$$^\dagger$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \leq n \leq 10^5$$$) — the length of the permutation $$$p$$$.

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

Output format:
For each test case, output $$$p_1, p_2, \ldots, p_n$$$.

If there are multiple solutions, you may output any one of them.

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

Note:
In the first test case, $$$p=[4,1,2,3]$$$ is a valid permutation. However, the permutation $$$p=[1,2,3,4]$$$ is not a valid permutation as we can choose $$$i=1$$$ and $$$j=3$$$. Then $$$p_1=1$$$ divides $$$p_3=3$$$ and $$$p_2=2$$$ divides $$$p_4=4$$$. Note that the permutation $$$p=[3, 4, 2, 1]$$$ is also not a valid permutation as we can choose $$$i=3$$$ and $$$j=2$$$. Then $$$p_3=2$$$ divides $$$p_2=4$$$ and $$$p_4=1$$$ divides $$$p_3=2$$$.

In the second test case, $$$p=[1,2,3]$$$ is a valid permutation. In fact, all $$$6$$$ permutations of length $$$3$$$ are valid.

Example input:
2
4
3

Example output:
4 1 2 3
1 2 3

Editorial:
Lexicographically Largest
Contest: think-cell Round 1
Difficulty rating: 1700
Tags: binary search, constructive algorithms, data structures, greedy, sortings

Stack has an array $$$a$$$ of length $$$n$$$. He also has an empty set $$$S$$$. Note that $$$S$$$ is not a multiset.

He will do the following three-step operation exactly $$$n$$$ times:

1. Select an index $$$i$$$ such that $$$1 \leq i \leq |a|$$$.
2. Insert$$$^\dagger$$$ $$$a_i + i$$$ into $$$S$$$.
3. Delete $$$a_i$$$ from $$$a$$$. Note that the indices of all elements to the right of $$$a_i$$$ will decrease by $$$1$$$.

Note that after $$$n$$$ operations, $$$a$$$ will be empty.

Stack will now construct a new array $$$b$$$ which is $$$S$$$ sorted in decreasing order. Formally, $$$b$$$ is an array of size $$$|S|$$$ where $$$b_i$$$ is the $$$i$$$-th largest element of $$$S$$$ for all $$$1 \leq i \leq |S|$$$.

Find the lexicographically largest$$$^\ddagger$$$ $$$b$$$ that Stack can make.

$$$^\dagger$$$ A set can only contain unique elements. Inserting an element that is already present in a set will not change the elements of the set.

$$$^\ddagger$$$ An array $$$p$$$ is lexicographically larger than a sequence $$$q$$$ if and only if one of the following holds:

- $$$q$$$ is a prefix of $$$p$$$, but $$$p \ne q$$$; or
- in the first position where $$$p$$$ and $$$q$$$ differ, the array $$$p$$$ has a larger element than the corresponding element in $$$q$$$.

Note that $$$[3,1,4,1,5]$$$ is lexicographically larger than $$$[3,1,3]$$$, $$$[\,]$$$, and $$$[3,1,4,1]$$$ but not $$$[3,1,4,1,5,9]$$$, $$$[3,1,4,1,5]$$$, and $$$[4]$$$.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.

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

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_{n}$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of array $$$a$$$.

The sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, output the lexicographically largest $$$b$$$.

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

Note:
In the first test case, select $$$i=1$$$ in the first operation, insert $$$a_1 + 1 = 3$$$ in $$$S$$$, and delete $$$a_1$$$ from $$$a$$$. After the first operation, $$$a$$$ becomes $$$a=[1]$$$. In the second operation, we select $$$i=1$$$ again and insert $$$a_1 + 1 = 2$$$ in $$$S$$$. Thus $$$S=\{2, 3\}$$$, and $$$b = [3, 2]$$$.

Note that if you select $$$i=2$$$ in the first operation, and $$$i=1$$$ in the second operation, $$$S=\{3\}$$$ as $$$3$$$ will be inserted twice, resulting in $$$b=[3]$$$.

As $$$[3,2]$$$ is lexicographically larger than $$$[3]$$$, we should select $$$i=1$$$ in the first operation.

In the second test case, in each operation, select the last element.

Example input:
3
2
2 1
5
1 100 1000 1000000 1000000000
3
6 4 8

Example output:
3 2 
1000000005 1000004 1003 102 2 
11 7 6

Editorial:
Sum over all Substrings (Easy Version)
Contest: think-cell Round 1
Difficulty rating: 1800
Tags: brute force, dp, greedy, strings

This is the easy version of the problem. The only difference between the two versions is the constraint on $$$t$$$ and $$$n$$$. You can make hacks only if both versions of the problem are solved.

For a binary$$$^\dagger$$$ pattern $$$p$$$ and a binary string $$$q$$$, both of length $$$m$$$, $$$q$$$ is called $$$p$$$-good if for every $$$i$$$ ($$$1 \leq i \leq m$$$), there exist indices $$$l$$$ and $$$r$$$ such that:

- $$$1 \leq l \leq i \leq r \leq m$$$, and
- $$$p_i$$$ is a mode$$$^\ddagger$$$ of the string $$$q_l q_{l+1} \ldots q_{r}$$$.

For a pattern $$$p$$$, let $$$f(p)$$$ be the minimum possible number of $$$\mathtt{1}$$$s in a $$$p$$$-good binary string (of the same length as the pattern).

You are given a binary string $$$s$$$ of size $$$n$$$. Find $$$$$$\sum_{i=1}^{n} \sum_{j=i}^{n} f(s_i s_{i+1} \ldots s_j).$$$$$$ In other words, you need to sum the values of $$$f$$$ over all $$$\frac{n(n+1)}{2}$$$ substrings of $$$s$$$.

$$$^\dagger$$$ A binary pattern is a string that only consists of characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.

$$$^\ddagger$$$ Character $$$c$$$ is a mode of string $$$t$$$ of length $$$m$$$ if the number of occurrences of $$$c$$$ in $$$t$$$ is at least $$$\lceil \frac{m}{2} \rceil$$$. For example, $$$\mathtt{0}$$$ is a mode of $$$\mathtt{010}$$$, $$$\mathtt{1}$$$ is not a mode of $$$\mathtt{010}$$$, and both $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$ are modes of $$$\mathtt{011010}$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of the binary string $$$s$$$.

The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$ consisting of only characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.

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

Output format:
For each test case, output the sum of values of $$$f$$$ over all substrings of $$$s$$$.

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

Note:
In the first test case, the only $$$\mathtt{1}$$$-good string is $$$\mathtt{1}$$$. Thus, $$$f(\mathtt{1})=1$$$.

In the second test case, $$$f(\mathtt{10})=1$$$ because $$$\mathtt{01}$$$ is $$$\mathtt{10}$$$-good, and $$$\mathtt{00}$$$ is not $$$\mathtt{10}$$$-good. Thus, the answer is $$$f(\mathtt{1})+f(\mathtt{10})+f(\mathtt{0}) = 1 + 1 + 0 = 2$$$.

In the third test case, $$$f$$$ equals to $$$0$$$ for all $$$1 \leq i \leq j \leq 5$$$. Thus, the answer is $$$0$$$.

Example input:
4
1
1
2
10
5
00000
20
11110110000000111111

Example output:
1
2
0
346

Editorial:
Sum over all Substrings (Hard Version)
Contest: think-cell Round 1
Difficulty rating: 2100
Tags: bitmasks, divide and conquer, dp, dsu, greedy, implementation, strings

This is the hard version of the problem. The only difference between the two versions is the constraint on $$$t$$$ and $$$n$$$. You can make hacks only if both versions of the problem are solved.

For a binary$$$^\dagger$$$ pattern $$$p$$$ and a binary string $$$q$$$, both of length $$$m$$$, $$$q$$$ is called $$$p$$$-good if for every $$$i$$$ ($$$1 \leq i \leq m$$$), there exist indices $$$l$$$ and $$$r$$$ such that:

- $$$1 \leq l \leq i \leq r \leq m$$$, and
- $$$p_i$$$ is a mode$$$^\ddagger$$$ of the string $$$q_l q_{l+1} \ldots q_{r}$$$.

For a pattern $$$p$$$, let $$$f(p)$$$ be the minimum possible number of $$$\mathtt{1}$$$s in a $$$p$$$-good binary string (of the same length as the pattern).

You are given a binary string $$$s$$$ of size $$$n$$$. Find $$$$$$\sum_{i=1}^{n} \sum_{j=i}^{n} f(s_i s_{i+1} \ldots s_j).$$$$$$ In other words, you need to sum the values of $$$f$$$ over all $$$\frac{n(n+1)}{2}$$$ substrings of $$$s$$$.

$$$^\dagger$$$ A binary pattern is a string that only consists of characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.

$$$^\ddagger$$$ Character $$$c$$$ is a mode of string $$$t$$$ of length $$$m$$$ if the number of occurrences of $$$c$$$ in $$$t$$$ is at least $$$\lceil \frac{m}{2} \rceil$$$. For example, $$$\mathtt{0}$$$ is a mode of $$$\mathtt{010}$$$, $$$\mathtt{1}$$$ is not a mode of $$$\mathtt{010}$$$, and both $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$ are modes of $$$\mathtt{011010}$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The description of the test cases follows.

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

The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$ consisting of only characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.

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

Output format:
For each test case, output the sum of values of $$$f$$$ over all substrings of $$$s$$$.

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

Note:
In the first test case, the only $$$\mathtt{1}$$$-good string is $$$\mathtt{1}$$$. Thus, $$$f(\mathtt{1})=1$$$.

In the second test case, $$$f(\mathtt{10})=1$$$ because $$$\mathtt{01}$$$ is $$$\mathtt{10}$$$-good, and $$$\mathtt{00}$$$ is not $$$\mathtt{10}$$$-good. Thus, the answer is $$$f(\mathtt{1})+f(\mathtt{10})+f(\mathtt{0}) = 1 + 1 + 0 = 2$$$.

In the third test case, $$$f$$$ equals to $$$0$$$ for all $$$1 \leq i \leq j \leq 5$$$. Thus, the answer is $$$0$$$.

Example input:
4
1
1
2
10
5
00000
20
11110110000000111111

Example output:
1
2
0
346

Editorial:
2..3...4.... Wonderful! Wonderful!
Contest: think-cell Round 1
Difficulty rating: 2400
Tags: combinatorics, dp, math

Stack has an array $$$a$$$ of length $$$n$$$ such that $$$a_i = i$$$ for all $$$i$$$ ($$$1 \leq i \leq n$$$). He will select a positive integer $$$k$$$ ($$$1 \leq k \leq \lfloor \frac{n-1}{2} \rfloor$$$) and do the following operation on $$$a$$$ any number (possibly $$$0$$$) of times.

- Select a subsequence$$$^\dagger$$$ $$$s$$$ of length $$$2 \cdot k + 1$$$ from $$$a$$$. Now, he will delete the first $$$k$$$ elements of $$$s$$$ from $$$a$$$. To keep things perfectly balanced (as all things should be), he will also delete the last $$$k$$$ elements of $$$s$$$ from $$$a$$$.

Stack wonders how many arrays $$$a$$$ can he end up with for each $$$k$$$ ($$$1 \leq k \leq \lfloor \frac{n-1}{2} \rfloor$$$). As Stack is weak at counting problems, he needs your help.

Since the number of arrays might be too large, please print it modulo $$$998\,244\,353$$$.

$$$^\dagger$$$ A sequence $$$x$$$ is a subsequence of a sequence $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by deleting several (possibly, zero or all) elements. For example, $$$[1, 3]$$$, $$$[1, 2, 3]$$$ and $$$[2, 3]$$$ are subsequences of $$$[1, 2, 3]$$$. On the other hand, $$$[3, 1]$$$ and $$$[2, 1, 3]$$$ are not subsequences of $$$[1, 2, 3]$$$.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^3$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \leq n \leq 10^6$$$) — the length of the array $$$a$$$.

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

Output format:
For each test, on a new line, print $$$\lfloor \frac{n-1}{2} \rfloor$$$ space-separated integers — the $$$i$$$-th integer representing the number of arrays modulo $$$998\,244\,353$$$ that Stack can get if he selects $$$k=i$$$.

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

Note:
In the first test case, two $$$a$$$ are possible for $$$k=1$$$:

- $$$[1,2,3]$$$;
- $$$[2]$$$.

In the second test case, four $$$a$$$ are possible for $$$k=1$$$:

- $$$[1,2,3,4]$$$;
- $$$[1,3]$$$;
- $$$[2,3]$$$;
- $$$[2,4]$$$.

In the third test case, two $$$a$$$ are possible for $$$k=2$$$:

- $$$[1,2,3,4,5]$$$;
- $$$[3]$$$.

Example input:
4
3
4
5
10

Example output:
2 
4 
10 2 
487 162 85 10

Editorial:
Maximize the Difference
Contest: think-cell Round 1
Difficulty rating: 2700
Tags: bitmasks, brute force, dfs and similar

For an array $$$b$$$ of $$$m$$$ non-negative integers, define $$$f(b)$$$ as the maximum value of $$$\max\limits_{i = 1}^{m} (b_i | x) - \min\limits_{i = 1}^{m} (b_i | x)$$$ over all possible non-negative integers $$$x$$$, where $$$|$$$ is bitwise OR operation.

You are given integers $$$n$$$ and $$$q$$$. You start with an empty array $$$a$$$. Process the following $$$q$$$ queries:

- $$$v$$$: append $$$v$$$ to the back of $$$a$$$ and then output $$$f(a)$$$. It is guaranteed that $$$0 \leq v < n$$$.

The queries are given in a modified way.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n \leq 2^{22}$$$, $$$1 \leq q \leq 10^6$$$) — the number of queries.

The second line of each test case contains $$$q$$$ space-separated integers $$$e_1,e_2,\ldots,e_q$$$ ($$$0 \leq e_i < n$$$) — the encrypted values of $$$v$$$.

Let $$$\mathrm{last}_i$$$ equal the output of the $$$(i-1)$$$-th query for $$$i\geq 2$$$ and $$$\mathrm{last}_i=0$$$ for $$$i=1$$$. Then the value of $$$v$$$ for the $$$i$$$-th query is ($$$e_i + \mathrm{last}_i$$$) modulo $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2^{22}$$$ and the sum of $$$q$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, print $$$q$$$ integers. The $$$i$$$-th integer is the output of the $$$i$$$-th query.

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

Note:
In the first test case, the final $$$a=[1,2]$$$. For $$$i=1$$$, the answer is always $$$0$$$, irrespective of $$$x$$$. For $$$i=2$$$, we can select $$$x=5$$$.

In the second test case, the final $$$a=[3,1,0,5]$$$.

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

Example output:
0 2
0 2 3 5

Editorial:
Prefix Max Set Counting
Contest: think-cell Round 1
Difficulty rating: 3100
Tags: data structures, dp, trees

Define a function $$$f$$$ such that for an array $$$b$$$, $$$f(b)$$$ returns the array of prefix maxima of $$$b$$$. In other words, $$$f(b)$$$ is an array containing only those elements $$$b_i$$$, for which $$$b_i=\max(b_1,b_2,\ldots,b_i)$$$, without changing their order. For example, $$$f([3,10,4,10,15,1])=[3,10,10,15]$$$.

You are given a tree consisting of $$$n$$$ nodes rooted at $$$1$$$.

A permutation$$$^\dagger$$$ $$$p$$$ of is considered a pre-order of the tree if for all $$$i$$$ the following condition holds:

- Let $$$k$$$ be the number of proper descendants$$$^\ddagger$$$ of node $$$p_i$$$.
- For all $$$x$$$ such that $$$i < x \leq i+k$$$, $$$p_x$$$ is a proper descendant of node $$$p_i$$$.

Find the number of distinct values of $$$f(a)$$$ over all possible pre-orders $$$a$$$. Since this value might be large, you only need to find it modulo $$$998\,244\,353$$$.

$$$^\dagger$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

$$$^\ddagger$$$ Node $$$t$$$ is a proper descendant of node $$$s$$$ if $$$s \neq t$$$ and $$$s$$$ is on the unique simple path from $$$t$$$ to $$$1$$$.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — the number of vertices.

The following next $$$n-1$$$ lines contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$) — denoting an edge between nodes $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.

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

Output format:
For each test case, output the number of distinct values of $$$f(a)$$$ modulo $$$998\,244\,353$$$ that you can get.

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

Note:
In the first test case, the only valid pre-order is $$$a=[1]$$$. So the only possible value of $$$f(a)$$$ is $$$[1]$$$.

In the second test case, the only valid pre-order is $$$a=[1,2]$$$. So the only possible value $$$f(a)$$$ is $$$[1,2]$$$.

In the third test case, the two valid pre-orders are $$$a=[1,2,3]$$$ and $$$a=[1,3,2]$$$. So the possible values of $$$f(a)$$$ are $$$[1,2,3]$$$ and $$$[1,3]$$$.

In the fifth test case, the possible values of $$$f(a)$$$ are:

- $$$[1,5]$$$;
- $$$[1,2,5]$$$;
- $$$[1,3,5]$$$;
- $$$[1,4,5]$$$;
- $$$[1,2,3,5]$$$;
- $$$[1,2,4,5]$$$;
- $$$[1,3,4,5]$$$;
- $$$[1,2,3,4,5]$$$.

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

Example output:
1
1
2
1
8
6

Editorial:
Counting Is Fun
Contest: think-cell Round 1
Difficulty rating: 3500
Tags: combinatorics

You are given a binary$$$^\dagger$$$ pattern $$$p$$$ of length $$$n$$$.

A binary string $$$q$$$ of the same length $$$n$$$ is called good if for every $$$i$$$ ($$$1 \leq i \leq n$$$), there exist indices $$$l$$$ and $$$r$$$ such that:

- $$$1 \leq l \leq i \leq r \leq n$$$, and
- $$$p_i$$$ is a mode$$$^\ddagger$$$ of the string $$$q_lq_{l+1}\ldots q_r$$$.

Count the number of good binary strings modulo $$$998\,244\,353$$$.

$$$^\dagger$$$ A binary string is a string that only consists of characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.

$$$^\ddagger$$$ Character $$$c$$$ is a mode of string $$$t$$$ of length $$$m$$$ if the number of occurrences of $$$c$$$ in $$$t$$$ is at least $$$\lceil \frac{m}{2} \rceil$$$. For example, $$$\mathtt{0}$$$ is a mode of $$$\mathtt{010}$$$, $$$\mathtt{1}$$$ is not a mode of $$$\mathtt{010}$$$, and both $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$ are modes of $$$\mathtt{011010}$$$.

Input format:
The first line of input contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the binary string $$$p$$$.

The second line of input contains a binary string $$$p$$$ of length $$$n$$$ consisting of characters 0 and 1.

Output format:
Output the number of good strings modulo $$$998\,244\,353$$$.

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

Note:
In the second example, the good strings are

- $$$\mathtt{010}$$$;
- $$$\mathtt{011}$$$;
- $$$\mathtt{101}$$$;
- $$$\mathtt{110}$$$;
- $$$\mathtt{111}$$$.

Example input:
1
0

Example output:
1

Example input:
3
111

Example output:
5

Editorial:
Cut Ribbon
Contest: Codeforces Round 119 (Div. 2)
Difficulty rating: 1300
Tags: brute force, dp

Polycarpus has a ribbon, its length is n. He wants to cut the ribbon in a way that fulfils the following two conditions:

- After the cutting each ribbon piece should have length a, b or c.
- After the cutting the number of ribbon pieces should be maximum.

Help Polycarpus and find the number of ribbon pieces after the required cutting.

Input format:
The first line contains four space-separated integers n, a, b and c (1 ≤ n, a, b, c ≤ 4000) — the length of the original ribbon and the acceptable lengths of the ribbon pieces after the cutting, correspondingly. The numbers a, b and c can coincide.

Output format:
Print a single number — the maximum possible number of ribbon pieces. It is guaranteed that at least one correct ribbon cutting exists.

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

Note:
In the first example Polycarpus can cut the ribbon in such way: the first piece has length 2, the second piece has length 3.

In the second example Polycarpus can cut the ribbon in such way: the first piece has length 5, the second piece has length 2.

Example input:
5 5 3 2

Example output:
2

Example input:
7 5 5 2

Example output:
2

Editorial:
Counting Rhombi
Contest: Codeforces Round 119 (Div. 2)
Difficulty rating: 1300
Tags: brute force, math

You have two positive integers w and h. Your task is to count the number of rhombi which have the following properties:

- Have positive area.
- With vertices at integer points.
- All vertices of the rhombi are located inside or on the border of the rectangle with vertices at points (0, 0), (w, 0), (w, h), (0, h). In other words, for all vertices (xi, yi) of the rhombus the following conditions should fulfill: 0 ≤ xi ≤ w and 0 ≤ yi ≤ h.
- Its diagonals are parallel to the axis.

Count the number of such rhombi.

Let us remind you that a rhombus is a quadrilateral whose four sides all have the same length.

Input format:
The first line contains two integers w and h (1 ≤ w, h ≤ 4000) — the rectangle's sizes.

Output format:
Print a single number — the number of sought rhombi.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

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

Note:
In the first example there exists only one such rhombus. Its vertices are located at points (1, 0), (2, 1), (1, 2), (0, 1).

Example input:
2 2

Example output:
1

Example input:
1 2

Example output:
0

Editorial: