Recently, Joseph bought lots of books and was going to put them all on the shelf. He found that there are only two types of books – the type A with height $$$a$$$ and thickness $$$1$$$, and the type B with height $$$b~(a \lt b)$$$ and thickness $$$1$$$. The number of each type of book are $$$n$$$ and $$$m$$$ respectively. And he already knew the height of the bookshelf which is $$$h~(h \geq b)$$$.

In the beginning, he arranged all the books on the shelf in height-ascending order, which means the books of height $$$a$$$ are all on the left, and the books of height $$$b$$$ are all on the right. The total length these books occupied on the bookshelf will be $$$n + m$$$.

However, Joseph found there was still a vacancy on top of these books, so he prepared to select $$$k ~ (0 \leq k \leq m - 1)$$$ books with height $$$b$$$ from the rightmost side and put them all horizontally on top of other books to reduce the length they occupied. He wanted to know the minimum width if he arranges these books optimally.

$$$Fish$$$ is a working-class citizen, he works for company H(Heinz). One day, $$$Fish$$$ wants to know how much his coworkers like him.

After some research, $$$Fish$$$ organized the results into a string $$$S$$$

1.  when $$$S_{i}=1$$$, this means that the $$$i$$$th worker likes Fish.
2.  when $$$S_{i}=0$$$, this means that the $$$i$$$th worker dislikes Fish.

After researching，$$$Fish$$$ copied down $$$S_{l...r}$$$ as a new string $$$T$$$，and saw that there were many 0s among $$$T$$$, he became very sad. So he wished to insert some $$$1$$$ to any position of $$$T$$$ in order to make himself happier.

If the length of $$$T$$$ is $$$m$$$ after inserts，$$$Fish$$$ would become sad under either of the following two conditions:

1.  there exists a $$$p~(1\leq p \leq m)$$$ which the number of 0 are strictly larger than the number of 1 within $$$T_1$$$ to $$$T_p$$$.
2.  there exists a $$$p~(1\leq p \leq m)$$$ which the number of 0 are strictly larger than the number of 1 within $$$T_p$$$ to $$$T_m$$$.

$$$Fish$$$ also doesn't know for certain the value of $$$l$$$ and $$$r$$$, so he wants to know with $$$q$$$ possible pairs of $$$l$$$ and $$$r$$$, the least number of inserts that Fish needs to make in order to make himself happy.

You are given a tree of $$$n$$$ nodes, the i-th node has value $$$a_i$$$.

Define a node $$$t$$$ is valid, if you can divide the $$$n$$$ nodes into two sets $$$A$$$ and $$$B$$$, such that the following condition would hold:

• $$$\forall u,v\in A(u\neq v)$$$, if $$$u$$$ is on the path from $$$t$$$ to $$$v$$$, then $$$a_u \lt a_v$$$
• $$$\forall u,v\in B(u\neq v)$$$, if $$$u$$$ is on the path from $$$t$$$ to $$$v$$$, then $$$a_u \gt a_v$$$

You need to find out whether the node $$$1$$$ is valid.

Joseph loves physics. And one day, while Joseph was playing ping-pong, he was obsessed with the study of the collision of two balls.

He found the collision of any two of the balls is completely elastic, which means there is no kinetic energy loss and the sum of the momentum remains the same after the collision.

However, you only need to consider a simpler case in this problem. If we regard all ping-pong balls as the circles of radius $$$1$$$ on the two-dimensional plane, the collision of a moving ball and a static ball can be described by the figure below. Ball $$$O_1$$$ has the speed $$$\boldsymbol{u}$$$ initially, and then it hits a static ball $$$O_2$$$ at the point $$$P$$$. Let the tangent(切线) of circle $$$O_2$$$ at point $$$P$$$ be $$$l$$$. The speed of ball $$$O_2$$$ after collision will be a speed of $$$\boldsymbol{v}$$$ which is perpendicular(垂直) to $$$l$$$.

Particularly, if the trail of $$$O_1$$$ is just tangent to $$$O_2$$$ (see the figure below), there will be no collision.

Now Joseph put three static balls $$$O_1, O_2, O_3$$$ on the table. He wants to give the ball $$$O_1$$$ an initial speed $$$u$$$ and see if it can hit $$$O_2$$$ and let $$$O_2$$$ finally hit $$$O_3$$$. Please write a program to tell him whether the initial speed exists.

Megumi is a girl who loves number theory. Today is her birthday, so Joseph creates a new function $$$f(n)$$$ and gives it to her as a gift. The definition of $$$f(n)$$$ is shown in the formula as follows.

$$$$$$ f(n) = \prod_{i = 1}^m p_i^{a_i \% 2} $$$$$$

where $$$p_1,p_2,\cdots,p_m~(p_1 \lt p_2 \lt \cdots \lt p_m)$$$ are prime factors of $$$n$$$ and

$$$$$$ n = \prod_{i = 1}^m p_i^{a_i} $$$$$$

Now Joseph gives you $$$n$$$ integers $$$b_1, b_2, \cdots, b_n$$$ and wants you to calculate the following formula. $$$$$$ \left(\sum_{1\leq i \lt j \leq n} f\left(b_i \times b_j\right)\right)\mod (10^9+7) $$$$$$

342 likes playing Xiangqi (as it's called Chinese chess). His favorite piece in Xiangqi is "Xiang" because his opponents usually overlook the existence of Xiang so their major pieces are often taken by 342's Xiang.

For those of you who don't know how Xiang moves in Xiangqi, Xiang is a minor piece that each player initially has two, located at the position 3 and 6 respectively. The number for each position is showed in the illustration bellow. In a single move, Xiang should move 2 squares horizontally as well as vertically. But note that it can neither move out of the half board nor it can overlap with other pieces. The illustration below showed all the 7 possible positions that Xiang could reach. For example, in a single move,

Centered scaled image.

· A Xiang at position 2 can move to position 4,

· A Xiang at position 7 can move to position 6,

· A Xiang at position 3 cannot move to position 5.

342 has 2 Xiangs as the only 2 pieces in the half board. Their present positions are given and guaranteed to be 2 different positions out of the 7 possible ones. But 342 disliked the present positions of his 2 Xiangs and would like to adjust their positions by a few moves. In each move, he can choose one of the Xiangs and move it following the rules explained. The final positions 342 want are also given and guaranteed to be 2 different positions out of the 7 possible ones. Note that the 2 Xiangs are considered the same, meaning that he doesn't restrict that which of the 2 Xiangs has to move to which of the 2 positions.

Now 342 wonders, at least how many moves he need to adjust the 2 Xiangs from the present positions to the final positions that 342 want?

For her excellent performance, pianist Chevonne was awarded a pearl necklace. The necklace consisted of $$$n$$$ pearls which form a circle and are numbered $$$1, 2, \cdots, n$$$ clockwise.

To prevent the pearls from being covered with dust, she wants to move pearls from the necklace and wipe them. However, the way to remove the pearls is complex because of their uniqueness of them.

Specifically, every pearl on the necklace has a continuity value $$$c_i ~ (c_i \geq 0)$$$. Each turn, Chevonne can choose a pearl $$$i$$$ with $$$c_i \geq 1$$$ and move the pearl $$$i$$$ and $$$c_i - 1$$$ clockwise consecutive pearls ($$$c_i$$$ pearls in all). Be careful! If the number of remaining pearls is less than $$$c_i$$$, she will be unable to choose pearl $$$i$$$. After that, the remaining pearls will form a new circle.

Chevonne will repeat the process till she can't remove any pearls or all the pearls have been removed. She is curious about the maximum number of pearls she could remove and the number of such solutions.

Here, we use a set to describe a solution. The set contains the number $$$i$$$ if Chevonne chose pearl $$$i$$$ in some step. Two solutions are different if and only if the sets are different.

Paulliant is a linguist. Recently he received an article written in language A and he was told to translate it into language B. The two languages only differ in word order, so, Paulliant decided to translate by redefining the reading order of the articles, and came up with the following method.

Suppose that the article consists of $$$n$$$ words, numbered as $$$1,2,3\cdots n$$$. Paulliant generated a string $$$str$$$ consisting of only '(', ')' and '-', whose length is also $$$n$$$. The string must satisfy the rule of bracket matching. Formally speaking, define $$$s_{(i}$$$ and $$$s_{)i}$$$ , representing the number of character '(' or ')' within the first $$$i$$$ characters of the string, respectively, there is $$$s_{(i} \geq s_{)i}$$$ for every $$$1\leq i\leq n$$$ and $$$s_{(n}=s_{)n}$$$.

The process to read the article obeys the following rules.

(1) The process starts from the first word.

(2) For the $$$i$$$-th word, if $$$str_i$$$ is '-' or ')', then read the $$$i$$$-th word directly, and jump to the $$$(i+1)$$$-th word.

(3) For the $$$i$$$-th word, if $$$str_i$$$ is '(', then find the matching right bracket of it. Supposing it to be $$$str_j$$$, read the $$$(i+1)$$$-th to $$$j$$$-th word, then read the $$$i$$$-th word, and finally jump to the $$$(j+1)$$$-th word.

(4) If we are to read the $$$(n+1)$$$-th word (obviously it doesn't exist), the process ends.

Note that the process is recursive, meaning that when reading the $$$(i+1)$$$-th to $$$j$$$-th word in rule (2), it still follows the four rules.

For example,

· If $$$n=4$$$, $$$str$$$ is "(-)-", the reading order will be 2, 3, 1, 4.

· If $$$n=7$$$, $$$str$$$ is "-((-)-)", the reading order will be 1, 4, 5, 3, 6, 7, 2.

Now, give you the number of words $$$n$$$, and the string $$$str$$$ Paulliant generated. Your task is to print the reading order following the four rules. It can be proved that the reading order should be a permutation of numbers from $$$1$$$ to $$$n$$$.

Define function $$$f(n)$$$ to be the number of different arrays $$$a$$$ of positive integers, such that the sum of the elements in array $$$a$$$ equals to $$$n$$$.

For example, $$$f(3)=4$$$, and the four different arrays are $$$\{1,1,1\},\{1,2\},\{2,1\},\{3\}$$$.

You are given a positive integer $$$k$$$. Please find the answer of $$$f(k)$$$.

Joseph is playing a game with his friends. The game goes on a tree – a connected graph with $$$n$$$ vertices and $$$n - 1$$$ edges. The vertices are labeled by $$$1,2,\cdots,n$$$. The root of the tree is $$$1$$$.

There is a token initially on one of the vertices. At each step, Joseph will randomly choose a vertex from the $$$n$$$ vertices with equal probability, and then move the token according to the rules as follows:

Assume the token is currently on vertex $$$u$$$. And then vertex $$$v$$$ is selected by Joseph at random

• If $$$u$$$ is an ancestor of $$$v$$$, move the token to the vertex $$$v$$$.
• If $$$u$$$ is not an ancestor of $$$v$$$, move the token to the vertex $$$\texttt{LCA}(u,v)$$$. $$$\texttt{LCA}(u,v)$$$ denotes the lowest common ancestor of vectex $$$u$$$ and $$$v$$$.

There is also a target vertex $$$w$$$ in the tree. As soon as the token is moved to the target vertex, the game is over. Otherwise, the game will keep going until it hits the target vertex.

He wants to know the expected number of steps to hit the target when the token starts from each vertex.

Let's denote the expectation of steps starting from vertex $$$u$$$ modulo $$$10^9 + 7$$$ by $$$E(u)$$$. You are only expected to print $$$$$$ \sum_{u = 1}^{n} E(u) \oplus u $$$$$$

Monkey Joe likes to eat fruit. As monkey Joe is fond of climbing here and there, rather than eating fruits that are already in the grocery shops, he choose to climb the tree and eat the fruit on the tree.

A tree is a connected graph containing $$$n$$$ nodes and $$$n-1$$$ edges. On every node of the tree, there exists one single fruit. For a fruit on node $$$u$$$, it has a tiredness value of $$$val_{u}$$$.

Every time Joe eats the fruits, he only travels the simple path from $$$u$$$ to $$$v$$$ (a simple path is a path that every node and edge is visited only once). When he travels from $$$u$$$ to $$$v$$$, he will eat every fruit on the simple path. However, Joe gets very tired of eating all the fruits.

Formally, his tiredness of eating fruit $$$i$$$ that lies on the path from $$$u$$$ to $$$v$$$ is defined as $$$rank_{i} \times val_{i}$$$, where $$$rank_{i}$$$ denotes the rank of the fruit on node $$$i$$$ if you sort all the fruit on the simple path from $$$u$$$ to $$$v$$$ based on their tiredness values in increasing order. The whole tiredness of path ($$$u$$$, $$$v$$$) is the sum of the tiredness of eating every fruit on the path. It is guaranteed that the tiredness value of each fruit are distinct.

Joe is uncertain which path he would choose to climb, so he would like you to calculate the tiredness sum of all distinct paths of the tree. Since the answer may be very large, you only have to output the answer module $$$10^9+7$$$

Joseph developed an editing software called Pandote recently, and now he is testing it to make sure it works correctly, otherwise, he will probably get fired!

Joseph starts his testing by implementing copying and pasting as well as reversing operations to the string on the Pandote. More specifically, in each step, if the string on the screen is $$$S$$$, he will do the following operations in order.

1. Choose a prefix of length $$$l ~ (1 \leq l \leq |S|)$$$, then $$$S$$$ can be denoted by $$$AB~(|A|=l)$$$. Note that the string $$$B$$$ can be empty.
2. Swap the two parts and get the string $$$BA$$$.
3. Reverse the whole string and get the string $$$(BA)^r$$$

However, since the function of Pandote is limited, there are only two different lengths $$$l_1$$$ and $$$l_2$$$ of prefix he can choose in each step. Now Joseph wants to know whether he can convert the string $$$S$$$ to $$$T$$$ through several (possibly zero) steps.