#P17531. [JAG 2026 Summer Camp #1] Professor JAG' s Language
[JAG 2026 Summer Camp #1] Professor JAG' s Language
Problem Description
Professor JAG, a researcher of sequences, is developing a new expression language. You are given an integer and a string consisting of + and |. Throughout this problem, a sequence with elements is denoted by .
Consider the following expression:
Here, is the -th character of the input string and is used as the operator between and .
Since operator precedence is not defined, we consider all possible ways to fully parenthesize this expression without changing the order of its operands or operators. Each expression obtained in this way is called a valid expression.
For each expression , let denote the set of sequences represented by . The set is defined recursively as follows.
- If has the form
[i]for some (), then consists only of the one-element sequence . - If has the form
(X + Y), where and are its left and right subexpressions, then consists of every sequence obtained by concatenating a sequence in with a sequence in . For example, if contains and contains , then contains . - If has the form
(X | Y), where and are its left and right subexpressions, then .
Different valid expressions may represent the same sequence. Find the number of distinct sequences represented by at least one valid expression. Since the answer may be large, output it modulo .
Input Format
The input consists of a single test case in the following format.
N
O
The first line contains an integer (). The second line contains a string consisting of + and | ().
Output Format
Output the number of distinct sequences that can be represented, modulo .
4
+|+
4
7
||+|||
17
17
+|||+|+++||||+|+
1774
Hint
For the first sample, the expression is [1]+[2]|[3]+[4].
The following five valid expressions can be obtained by adding parentheses:
((([1]+[2])|[3])+[4])(([1]+[2])|([3]+[4]))(([1]+([2]|[3]))+[4])([1]+(([2]|[3])+[4]))([1]+([2]|([3]+[4])))
The following four distinct sequences are represented by at least one of these valid expressions:
Therefore, the answer is .