The owner of the pet shop has noticed that more and more pets are becoming lazy. In particular, the pigs do nothing but sleep all day, so half of the problem setter's fee has been deducted. The cats, on the other hand, have gradually learned to do nothing except sing "Hachimi". In order to correct the bad habits in the shop and make sure the pets actually learn something real, the owner decides to open an arithmetic class for them.

One day, the owner arranges $$$n^2$$$ pets into $$$n$$$ rows and $$$n$$$ columns, forming an $$$n\times n$$$ grid. Both rows and columns are numbered $$$1,2,\cdots,n$$$. The owner decides to play a small game to test the pets' arithmetic ability. Each pet keeps an integer, which is initially $$$0$$$. The owner will then issue $$$m$$$ commands in order, of the following four types:

• $$$\texttt{1 }k$$$: every pet adds $$$k$$$ to its number.
• $$$\texttt{2 }x\texttt{ }k$$$: every pet in row $$$x$$$ adds $$$k$$$ to its number.
• $$$\texttt{3 }y\texttt{ }k$$$: every pet in column $$$y$$$ adds $$$k$$$ to its number.
• $$$\texttt{4 }x\texttt{ }y$$$: the pet at row $$$x$$$, column $$$y$$$ reports its number.

After you solve this problem, the owner would like to remind you that the problems are not arranged in order of difficulty.

You are given a binary tree with $$$2n-1$$$ nodes, numbered from $$$1$$$ to $$$2n-1$$$.

Each node $$$p$$$ has two integer values $$$L_p$$$ and $$$R_p$$$ satisfying $$$L_p\le R_p$$$.

This binary tree satisfies the following properties:

• Node $$$1$$$ is the root, and $$$L_1=1$$$, $$$R_1=n$$$.
• For any node $$$p$$$:
  • If $$$L_p=R_p$$$, then node $$$p$$$ has no children.
  • If $$$L_p \lt R_p$$$, then node $$$p$$$ has two children. Here, we distinguish between the left child and the right child. Let $$$u$$$ be the left child and $$$v$$$ the right child; they satisfy $$$L_u=L_p$$$, $$$R_u+1=L_v$$$, and $$$R_v=R_p$$$.

For any interval $$$[l,r]$$$ with integer endpoints satisfying $$$1\le l\le r\le n$$$, consider the following algorithm: $$$$$$ \begin{array}{l} \textbf{function }\text{visit}(p,l,r,\textit{id})\\ \begin{array}{rl} 1&\textbf{if }r \lt L_p\text{ or }R_p \lt l\\ 2&\quad\textbf{return}\\ 3&\textit{cnt}_1[\textit{id}]\gets\textit{cnt}_1[\textit{id}]+1\\ 4&\textit{cnt}_2[p]\gets\textit{cnt}_2[p]+1\\ 5&\textbf{if }l\le L_p\text{ and }R_p\le r\\ 6&\quad\textbf{return}\\ 7&u\gets\text{left child of }p\\ 8&v\gets\text{right child of }p\\ 9&\text{visit}(u,l,r,\textit{id})\\ 10&\text{visit}(v,l,r,\textit{id}) \end{array} \end{array} $$$$$$ You are given $$$m$$$ intervals $$$[l_i,r_i]$$$ ($$$i=1,2,\cdots,m$$$). For each $$$i$$$, you call $$$\text{visit}(1,l_i,r_i,i)$$$ exactly once. All elements of the arrays $$$\textit{cnt}_1$$$ (indexed by $$$1,2,\cdots,m$$$) and $$$\textit{cnt}_2$$$ (indexed by $$$1,2,\cdots,2n-1$$$) are initially $$$0$$$. Your task is to find their final values.

You are given an undirected graph with $$$n$$$ vertices and $$$m$$$ edges. The vertices are numbered $$$1,2,\cdots,n$$$, and the edges are numbered $$$1,2,\cdots,m$$$.

You need to choose some of these edges.

We use a 01 sequence $$$\{a_i\}_{i=1}^m$$$ to represent which edges are chosen. If the edge with index $$$i$$$ is chosen, then $$$a_i=1$$$; otherwise, $$$a_i=0$$$.

The chosen edges must satisfy the following conditions:

• After keeping the chosen edges and removing all unchosen edges, the degree of every vertex is odd. This requirement may be impossible to satisfy; in that case, there is no solution.
• Under the above constraint, sequence $$$a$$$ must be lexicographically greatest.

Laplace Computing Center is trying to crack a warlock's code.

There are three operations. Your task is to use them to type out a given 01 string $$$S$$$.

The three operations are 0, 1, and B:

• Operation 0 means appending a 0 to the end of the current string.
• Operation 1 means appending a 1 to the end of the current string.
• Operation B means deleting the last character of the current string. In particular, if the current string is empty, this operation does nothing.

You must perform exactly $$$n$$$ operations and type out the given 01 string $$$S$$$.

Find the number of operation sequences that satisfy this requirement. Print the answer modulo $$$10^9+7$$$.

To verify whether the piglet is a reliable intermediate-level competitive programmer, Little L gives him the following problem.

Every positive integer $$$x$$$ can be uniquely written as $$$\overline{d_md_{m-1}\cdots d_0}$$$, satisfying all of the following conditions:

• $$$x=\sum\limits_{i=0}^m10^id_i$$$.
• $$$1\le d_m\le9$$$.
• For all $$$i\in\{0,1,\cdots,m-1\}$$$, $$$0\le d_i\le9$$$.

• None of $$$2,3,5,7$$$ is a divisor of $$$x$$$.
• For all $$$i\in\{0,1,\cdots,m-3\}$$$, at least one of the following holds: $$$d_{i+3}\ne2$$$, $$$d_{i+2}\ne0$$$, $$$d_{i+1}\ne2$$$, $$$d_i\ne5$$$.

Given positive integers $$$L$$$ and $$$R$$$ ($$$L\le R$$$), compute $$$\left(\sum\limits_{i=L}^Rf(i)\right)\bmod(10^9+7)$$$.

After competing in XCPC 2077, you realize that you have no hope of going any further.

You lie on your bed, close your eyes, and recall the scenes where you once fought hard in the contest hall.

Tears still come out. You are not willing to accept this; you feel that your team could have done better.

Suddenly, you wake up and find yourself back on the night before the contest.

Everything that happened before feels like a dream, yet it was so vivid.

You realize that this time, your team still has a chance.

You decide that this time, you will leave no regrets.

You are filled with determination.

Each XCPC contest lasts $$$300$$$ minutes.

There are $$$n$$$ problems. Their numeric indices are $$$1,2,\cdots,n$$$, and their letter indices are $$$\texttt{A},\texttt{B},\cdots$$$ in order.

It is known that problem $$$i$$$ takes $$$t_i$$$ minutes (not necessarily consecutive) to solve, and before solving it you will make exactly $$$d_i$$$ wrong submissions on this problem.

If problem $$$i$$$ cannot be solved even if you try your best, then $$$t_i=301$$$.

It is important to note that your team can work on only one problem in the same minute.

In the final standings, teams that solve more problems are ranked higher. Among teams that solve the same number of problems, those with a smaller penalty time are ranked higher.

Suppose a team solves problem $$$p_i$$$ at minute $$$s_i$$$ ($$$i=1,2,\cdots,m$$$), then the penalty time of this team is $$$$$$ \sum\limits_{i=1}^m(s_i+20d_{p_i}). $$$$$$ You need to find an optimal strategy — a strategy that maximizes the number of solved problems and, subject to that, minimizes the penalty time.

Little S has designed a problem and plans to give it as a gift to everyone.

You are given an integer sequence $$$a_1,a_2,\cdots,a_n$$$.

Output any non-empty subsequence $$$a_{b_1},a_{b_2},\cdots,a_{b_k}$$$ of this sequence that satisfies $$$$$$ \left(\sum_{i=1}^ka_{b_i}\right)\bmod n=0 $$$$$$ It can be shown that such a subsequence always exists.

After reading the problem, Little L explains some basic concepts to everyone:

For any integer $$$k$$$ satisfying $$$1\le k\le n$$$ and any integers $$$b_1,\dots,b_k$$$ satisfying $$$$$$ 1\le b_1 \lt b_2 \lt \cdots \lt b_k\le n $$$$$$ we say that $$$a_{b_1},a_{b_2},\cdots,a_{b_k}$$$ is a non-empty subsequence of $$$a_1,a_2,\cdots,a_n$$$.

Regarding the summation symbol $$$\sum$$$, its meaning is $$$$$$ \sum_{i=1}^ka_{b_i}=a_{b_1}+a_{b_2}+\cdots+a_{b_k} $$$$$$ Here, the operation $$$\bmod$$$ is defined as $$$$$$ x\bmod y=x-\left\lfloor\frac{x}{y}\right\rfloor y $$$$$$ where $$$\lfloor z\rfloor$$$ denotes the greatest integer less than or equal to $$$z$$$. The condition $$$x\bmod y=0$$$ is equivalent to saying that $$$x$$$ is a multiple of $$$y$$$.

Little L once encountered the following problem in a high school math quiz:

There is a staircase with $$$7$$$ steps. At each move, you may climb $$$1$$$ or $$$2$$$ steps. Find the probability of passing step $$$4$$$.

The reference solution was as follows:

Let $$$\textit{fib}_0=\textit{fib}_1=1$$$, and for $$$i\ge2$$$ let $$$\textit{fib}_i=\textit{fib}_{i-1}+\textit{fib}_{i-2}$$$. The answer is $$$\dfrac{\textit{fib}_4\cdot\textit{fib}_3}{\textit{fib}_7}=\dfrac{5}{7}$$$.

It assumes that all possible paths are equally likely. However, generally speaking, a person cannot directly choose one of the $$$\textit{fib}_7$$$ possible paths uniformly at random; instead, at each move, the person chooses to climb $$$1$$$ step or $$$2$$$ steps with equal probability (in particular, at step $$$6$$$, the person can only climb $$$1$$$ step).

To be rigorous, we restate the problem as follows:

There is a staircase with $$$7$$$ steps. A person wants to go from step $$$0$$$ to step $$$7$$$. At each move, the person climbs $$$1$$$ step with probability $$$\dfrac{1}{2}$$$, and $$$2$$$ steps with probability $$$\dfrac{1}{2}$$$. In particular, at step $$$6$$$, the person can only climb $$$1$$$ step. Find the probability of passing step $$$4$$$.

Consider drawing the probability tree, as shown in the following figure:

Now, consider a staircase with $$$n$$$ steps. A person wants to go from step $$$0$$$ to step $$$n$$$. At each move, the person climbs $$$1$$$ step with probability $$$\dfrac{1}{2}$$$, and $$$2$$$ steps with probability $$$\dfrac{1}{2}$$$. In particular, at step $$$n-1$$$, the person can only climb $$$1$$$ step. Find the probability of passing step $$$m$$$.

Print the answer modulo $$$10^9+7$$$ (a prime number).

Formally, it is easy to prove that the answer can be written as $$$\dfrac{p}{q}$$$. Here, $$$p$$$ is a non-negative integer, and $$$q$$$ is a positive integer that is not a multiple of $$$10^9+7$$$. You need to output $$$p\cdot q^{-1}\bmod(10^9+7)$$$, where $$$q^{-1}$$$ is an integer satisfying $$$q\cdot q^{-1}\equiv1\pmod{10^9+7}$$$. Modulo the prime number $$$10^9+7$$$, it is easy to prove that if $$$q^{-1}$$$ exists, then it is unique. According to Fermat's little theorem, $$$q^{-1}\equiv q^{10^9+5}\pmod{10^9+7}$$$.

You are given a graph with $$$n$$$ vertices, $$$m_1$$$ undirected edges, and $$$m_2$$$ directed edges. The vertices are numbered $$$1,2,\cdots,n$$$.

This graph satisfies the following property: For any subset of vertices, the number of edges (regardless of whether they are directed or undirected) whose both endpoints lie inside this subset does not exceed the size of the subset.

Count the number of ways to assign a direction to every undirected edge such that, after all undirected edges are oriented, the resulting graph contains no directed cycle. Print the answer modulo $$$10^9+7$$$.

It is guaranteed that the answer (before taking the modulo) is at least $$$1$$$. In particular, if $$$m_1=0$$$, the answer is $$$1$$$.

I keep recalling the days in the past over and over again, afraid that if I am even a little careless, those vivid moments will quietly slip away.

Fresh days are like newly peeled orange segments, falling onto the tip of your tongue; the sour and sweet juice spreads between your teeth, and even your breath carries a refreshing fruity scent. Sunshine also falls into your palm, soft and warm like a ball of fluff, slowly rolling away between your fingers. When you try to grasp it tightly, it has already slipped away, turning into faint glimmers among the dust.

Lovely days are like a soft warm breeze soaking into the afternoon, leaving a light trace of warmth on your collar. It brushes past that gentle silhouette, circling around, stirring a soft rustle in the flowers and leaves, then slows down again, only willing to drift slowly along the hem of your clothes. The patches of light around you quietly blur into a soft halo, and the air ripples with tenderness.

How could I bear to tuck all of these away into a drawer of the past, letting their vividness slowly fade into old shadows? I know that time must move forward, yet I still cannot help wishing it would slow down a little, then a little more, so that I can look once again at the shape of every single day.

Little L recalled $$$n$$$ days and used an uppercase English letter to describe each day.

He writes them down in order and obtains a string $$$S_1S_2\cdots S_n$$$ (each $$$S_i$$$ is an uppercase English letter).

We say that the $$$i$$$-th day is a fresh day if and only if exactly one of $$$S_i\ne S_{i-1}$$$ and $$$S_i\ne S_{i+1}$$$ holds.

We say that the $$$i$$$-th day is a lovely day if and only if neither of $$$S_i\ne S_{i-1}$$$ and $$$S_i\ne S_{i+1}$$$ holds.

It is important to note that we assume that $$$\boldsymbol{S_1\ne S_0}$$$ and $$$\boldsymbol{S_n\ne S_{n+1}}$$$ here.

Little L counted and found that there are $$$m_1$$$ fresh days and $$$m_2$$$ lovely days.

As time passed, Little L forgot the string $$$S_1S_2\cdots S_n$$$, and only vaguely remembers $$$n,m_1,m_2$$$.

Given $$$n,m_1,m_2$$$, determine whether Little L could have remembered them correctly or must have remembered them incorrectly.

If Little L could have remembered them correctly, output any possible string $$$S_1S_2\cdots S_n$$$.

Bored piglet has an integer sequence $$$a_1,a_2,\cdots,a_n$$$.

He wants to partition this sequence into several intervals, denoted as $$$[l_1,r_1],[l_2,r_2],\cdots,[l_m,r_m]$$$ (the value of $$$m$$$ is chosen arbitrarily), satisfying all of the following conditions:

• $$$l_1=1$$$, $$$r_m=n$$$.
• For every integer $$$i\in[1,m]$$$, $$$l_i\le r_i$$$; if $$$i\ne m$$$ then $$$r_i+1=l_{i+1}$$$.
• At least one of the following two conditions holds:
  • Condition A: for every integer $$$i\in[1,m]$$$, $$$a_{l_i}\le a_{l_i+1}\le\cdots\le a_{r_i}$$$.
  • Condition B: for every integer $$$i\in[1,m]$$$, $$$a_{l_i}\ge a_{l_i+1}\ge\cdots\ge a_{r_i}$$$.

There is no input in this problem; your program only needs to output a solution.

Formally, the state of a single qubit $$$\vert\psi\rangle$$$ can be written as $$$\alpha\vert0\rangle+\beta\vert1\rangle$$$, where $$$\alpha,\beta$$$ are complex numbers satisfying $$$\vert\alpha\vert^2+\vert\beta\vert^2=1$$$. Here, we regard this purely as an abstract mathematical object and do not discuss its physical meaning.

If we measure $$$\vert\psi\rangle$$$:

• With probability $$$\vert\alpha\vert^2$$$ we obtain the result $$$0$$$ and $$$\vert\psi\rangle$$$ collapses to $$$\vert0\rangle$$$ (that is, $$$1\cdot\vert0\rangle+0\cdot\vert1\rangle$$$).
• With probability $$$\vert\beta\vert^2$$$ we obtain the result $$$1$$$ and $$$\vert\psi\rangle$$$ collapses to $$$\vert1\rangle$$$ (that is, $$$0\cdot\vert0\rangle+1\cdot\vert1\rangle$$$).

Different qubits are not always separable. Consider the general state of a two-qubit system $$$$$$ \vert\psi_1\rangle\vert\psi_2\rangle=\alpha_{00}\vert0\rangle\vert0\rangle+\alpha_{01}\vert0\rangle\vert1\rangle+\alpha_{10}\vert1\rangle\vert0\rangle+\alpha_{11}\vert1\rangle\vert1\rangle $$$$$$ where $$$\vert\alpha_{00}\vert^2+\vert\alpha_{01}\vert^2+\vert\alpha_{10}\vert^2+\vert\alpha_{11}\vert^2=1$$$. If this expression cannot be factorized as $$$(\alpha\vert0\rangle+\beta\vert1\rangle)(\gamma\vert0\rangle+\delta\vert1\rangle)$$$, then we say that $$$\vert\psi_1\rangle$$$ and $$$\vert\psi_2\rangle$$$ are in an entangled state. Once an entangled state is formed, the correlation between the two qubits persists even if they are separated far apart in space.

If we measure $$$\vert\psi_1\rangle$$$ in this system:

• With probability $$$\vert\alpha_{00}\vert^2+\vert\alpha_{01}\vert^2$$$ we obtain the result $$$0$$$ and $$$\vert\psi_1\rangle\vert\psi_2\rangle$$$ collapses to $$$\dfrac{\vert0\rangle(\alpha_{00}\vert0\rangle+\alpha_{01}\vert1\rangle)}{\sqrt{\vert\alpha_{00}\vert^2+\vert\alpha_{01}\vert^2}}$$$.
• With probability $$$\vert\alpha_{10}\vert^2+\vert\alpha_{11}\vert^2$$$ we obtain the result $$$1$$$ and $$$\vert\psi_1\rangle\vert\psi_2\rangle$$$ collapses to $$$\dfrac{\vert1\rangle(\alpha_{10}\vert0\rangle+\alpha_{11}\vert1\rangle)}{\sqrt{\vert\alpha_{10}\vert^2+\vert\alpha_{11}\vert^2}}$$$.

Quantum gates are basic tools for manipulating qubits.

In this problem, you may use, and are only allowed to use, the H gate, X gate, Z gate, and CNOT gate.

To apply an H, X, or Z gate, you must choose a target qubit $$$\vert\psi\rangle$$$. Suppose before the operation $$$\vert\psi\rangle=\alpha\vert0\rangle+\beta\vert1\rangle$$$, then:

• The H gate transforms it into $$$\vert\psi\rangle=\alpha\dfrac{\vert0\rangle+\vert1\rangle}{\sqrt2}+\beta\dfrac{\vert0\rangle-\vert1\rangle}{\sqrt2}$$$.
• The X gate transforms it into $$$\vert\psi\rangle=\alpha\vert1\rangle+\beta\vert0\rangle$$$.
• The Z gate transforms it into $$$\vert\psi\rangle=\alpha\vert0\rangle-\beta\vert1\rangle$$$.

So he designs the $$$\mathcal{HYW}$$$ language — an extremely simple quantum programming language.

A $$$\mathcal{HYW}$$$ program consists of several statements, one per line. The interpreter executes the statements in order from top to bottom.

Statements are divided into measurement statements and operation statements.

A measurement statement has the form $$$\texttt{measure }x$$$, which means to measure $$$\vert\psi_x\rangle$$$. The measurement result is either $$$0$$$ or $$$1$$$.

An operation statement must be one of the following two types:

For example, suppose initially $$$\vert\psi_1\rangle\vert\psi_2\rangle=\vert0\rangle\vert0\rangle$$$. To make $$$\vert\psi_1\rangle\vert\psi_2\rangle=\dfrac{\vert0\rangle\vert0\rangle+\vert1\rangle\vert1\rangle}{\sqrt2}$$$, a $$$\mathcal{HYW}$$$ program can be:

H 1
CNOT 1 2

After each statement is executed, the state evolves as follows:

1. $$$\vert\psi_1\rangle\vert\psi_2\rangle=\dfrac{\vert0\rangle+\vert1\rangle}{\sqrt2}\vert0\rangle$$$.
2. $$$\vert\psi_1\rangle\vert\psi_2\rangle=\dfrac{\vert0\rangle\vert0\rangle+\vert1\rangle\vert1\rangle}{\sqrt2}$$$.

measure 1
if m1=1 then X 1
if m1=1 then X 2

After each statement is executed, the state evolves as follows:

1. It may be $$$\vert\psi_1\rangle\vert\psi_2\rangle=\vert0\rangle\vert0\rangle$$$ (if the measurement result is $$$0$$$), or it may be $$$\vert\psi_1\rangle\vert\psi_2\rangle=\vert1\rangle\vert1\rangle$$$ (if the measurement result is $$$1$$$).
2. It may be $$$\vert\psi_1\rangle\vert\psi_2\rangle=\vert0\rangle\vert0\rangle$$$, or it may be $$$\vert\psi_1\rangle\vert\psi_2\rangle=\vert0\rangle\vert1\rangle$$$.
3. $$$\vert\psi_1\rangle\vert\psi_2\rangle=\vert0\rangle\vert0\rangle$$$.

Initially, $$$\vert\psi_1\rangle=\alpha\vert0\rangle+\beta\vert1\rangle$$$, $$$\vert\psi_2\rangle=\vert0\rangle$$$, and $$$\vert\psi_3\rangle=\vert0\rangle$$$.

Your goal is to make $$$\vert\psi_1\rangle=\vert0\rangle$$$, $$$\vert\psi_2\rangle=\vert0\rangle$$$, and $$$\vert\psi_3\rangle=\alpha\vert0\rangle+\beta\vert1\rangle$$$.

You need to design a $$$\mathcal{HYW}$$$ program with at most $$$16$$$ statements to achieve this goal.