An Orz Panda team is participating a programming contest. They solved a problem mathematically but then they realized that this problem requires arbitrarily precision arithmetic (APA).

The Orz Pandas are too lazy to write APA themselves. They decide to use Java but as all we know Java do not support operator overloading. Soon their expression evolves to a monster:

a.add(b).remainder(M).multiply(d.substract(e.multiply(f)).add(g.divide(h))).multiply (BigInteger.ValueOf(233)) ... ...

Now can you write a tool to help the Orz Pandas to translate a normal C++ arithmetic expression into a Java BigInteger arithmetic expression?

An Orz Panda loves brute force algorithms. For example, he has wrote a C program solving Hanoi Tower problem:

(The source code rendering is broken for HTML. Please get it from attachment or PDF.)

#include <stdio.h>

void hanoi(long long size, char from, char to, char another)
{
    if (size == 0)
        return;
    hanoi(size - 1, from, another, to);
    printf("move     hanoi(size - 1, another, to, from);
}

int main()
{
    long long n;
    scanf("    hanoi(n, 'A', 'B', 'C');
    return 0;
}

Now you are given the number $$$n$$$, the input of the program. Please print the $$$k$$$-th line of its output.

Cai Xukun is a famous basketball star. He is known as the NBA Brand Ambassador in the 2019 Spring Festival. One day Cai Xukun wants to show his his basketball skill to the Orz Pandas. He would throw basketball from the point $$$\mathbf{P} = (x_0, y_0)$$$ to the hoop at the point $$$\mathbf{Q} = (x_1, y_1)$$$. The basketball's trajectory is a part of a ellipse (according to Kepler's First Law) but we can make a good approximation with a parabola:

$$$$$$\mathbf{B}(t) = \mathbf{P} + \mathbf{v}_0 t + \frac{1}{2} \mathbf{g} t^2$$$$$$

$$$\mathbf{v}_0 = (v_x, v_y)$$$ is the initial velocity. If at some time $$$t$$$, $$$\mathbf{B}(t) = \mathbf{Q}$$$, then Cai Xukun can throw the basketball into the hoop. Cai Xukun can only throw the basketball with an initial velocity not too large: $$$|\mathbf{v}_0| \leq v_{max}$$$.

Now the Orz Pandas will give you $$$\mathbf{P}$$$, $$$\mathbf{Q}$$$, and $$$v_{max}$$$. It's well-known that $$$\mathbf{g} = (0, -9.80665 m \cdot s^{-2})$$$. You should find an initial velocity vector $$$\mathbf{v}_0$$$ so that Cai Xukun can throw the basketball into the hoop, and the time $$$t$$$ when the basketball flies into the hoop.

Since Cai Xukun plays basketball so well, it's guaranteed that a solution exists.

Prof. Xie is a highly reputated scholar from SAST and the director of an important research program related to Orz Pandas. The Orz Pandas are telling a story of Prof. Xie to other pandas:

Once upon a time Prof. Xie wanted to buy a new house. He wanted the house to have $$$n$$$ features, and his spouse, Prof. Zhang wanted other $$$m$$$ features. Unfortunately, features wanted by Prof. Xie may conflict with features wanted by Prof. Zhang.

A panda wants to solve this situation mathematically. He assigns one weight $$$w_i$$$ for each feature $$$i$$$ and trys to choose some features with no conflicting pairs and maxmizing the sum of weights of choosen features.

Now you should tell him the maximized weight sum so he can check his solution.

The Orz Pandas has $$$n$$$ boxes in a line. Master wang9897 loves to repeat so he would do an operation on the boxes. He chooses a digit $$$x_i$$$ ($$$1 \leq x_i \leq 9$$$), and $$$3$$$ integers $$$l_i$$$, $$$r_i$$$, and $$$c_i$$$. Then he'll write an integer $$$\overline{x_i x_i x_i \cdots x_i}$$$ (there are $$$c_i + k$$$ digits) on a paper strip, and throw it into the $$$(l_i + k - 1)$$$-th box, for each $$$k \in \{1, 2, \cdots, r_i - l_i + 1\}$$$.

But Master qkoqhh loves gambling so he would do another kind of operation. He chooses two integers $$$l_i$$$, $$$r_i$$$, and randomly picks up one paper strip in a box between the $$$l_i$$$-th one and the $$$r_i$$$-th one. Each paper strip has same probability to be chosen. Now an Orz Panda wants to know the expectation of the integer on the paper strip picked up by qkoqhh.

To avoid floating-point errors, you should output the answer modulo $$$M = 1000000007$$$. If the expectation is $$$u/d$$$, you should output $$$(u \cdot d^{-1}) \mod M$$$.

An Orz Panda is researching fullerene. A fullerene is an allotrope of carbon whose molecule consists of carbon atoms connected by single and double bonds so as to form a closed or partially closed mesh, with fused rings of five to seven atoms.

The Orz Panda only cares about buckyball, the fullerene molecule with $$$60$$$ carbon atoms. Buckyball is a highly symmetric molecule looking like a association football ("soccer"), having $$$12$$$ pentagons and $$$20$$$ hexagons. You can view (and rotate) its geometry structure at http://acm.xidian.edu.cn/orz-panda/2019/supplementary/c60-3d/.

The Orz Panda has $$$n$$$ different types of atoms which can be attached on a carbon atom in the buckyball. On each carbon atom it's only allowed to attach at most one atom. Now wym6912 wants to know how many different molecules can be derived by attach some atoms on a buckyball, mathematically (so you don't need to figure out if a derivative is stable enough to exist). Two derivative are considered same if and only if it's possible to rotate one in the three-dimensional space so that it coincides with another.

Note that some derivatives may be chiral and mirroring is not a rotation in the three-dimensional space.

The Orz Panda can't answer wym6912's question. Please help him. Since the answer may be very large, you should output the answer modulo $$$1000000007$$$.

Orz Pandas have invented an interesting game. Now Masters wang9897 and qkoqhh are playing this game.

This game is played in $$$n$$$ rooms. In the beginning of the game qkoqhh would create a pile containing $$$x$$$ stones using a magic. Then wang9897 will choose two numbers $$$l$$$, $$$r$$$ ($$$1 \leq l \leq r \leq n$$$). There are many piles of stones in each room. The Orz Pandas have a magic to duplicate a pile so there may be many piles with the same size. qkoqhh can choose exactly $$$1$$$ or $$$0$$$ piles from each room between the $$$l$$$-th one and the $$$r$$$-th one (inclusively).

After that wang9897 and qkoqhh will play Nim game on all the piles created or chosen by qkoqhh. wang9897 will take the first move.

Now qkoqhh knows the value of $$$n$$$ and $$$x$$$. For each pile in one of the rooms, he knows its size and the room where it is. While wang9897 is chosing $$$l$$$ and $$$r$$$, qkoqhh will ask the Orz Pandas $$$Q$$$ questions. The $$$i$$$-th question is:

"How many ways can I choose the piles in the rooms to win the game, if wang9897 chooses the number $$$l_i$$$ and $$$r_i$$$?"

To solve this problem and get a balloon, you have to answer all the questions for the Orz Pandas. Note that even if two piles have the same number of stones, they should be considered as two different piles.

In case you don't know Nim game, its rule is given:

• In each move, the player taking the move must choose a non-empty pile and remove some (at least one) stones from it. It's allowed to remove all the stones in a pile.
• The two players take turns to move. wang9897 takes the first move, and qkoqhh takes the second move, etc.
• The player who can not take any move in his turn loses the game.

Horton is a famous swimmer, just like Cai Xukun is a famous basketball player. He swims slowly but he can make rumours as fast as Hong Kong journalists.

Now Horton is making fake news about Orz Pandas. To respond the fake news quickly, the Orz Pandas assembled a team containing $$$n$$$ Orz Pandas. It will cost $$$a_i$$$ dollar to build a data link between the $$$x_i$$$-th and the $$$y_i$$$-th Orz Pandas with a reliability of $$$b_i$$$.

The Orz Pandas want to build some data links so that each Orz Panda can communicate with all Orz Pandas in the responding team through a path of data links. If there are multiple ways to choose the data links to be built, the Orz Pandas wants to choose a subset $$$S$$$ of all possible data links to maximize

$$$$$$f(S) = \frac{\sum_{(x_i, y_i) \in S} b_i}{\sum_{(x_i, y_i) \in S} a_i}$$$$$$

Can you help the Orz Pandas to find the maximized $$$f(S)$$$?

The University of Electronic Science and Technology of Orz Pandas (UESTOP) has recently implemented IPv6 protocol for the campus computer network. An IPv6 address is an 128-bit unsigned integer, for example $$$x = 42540578239448488099419523072699400193$$$.

Certainly it's hard to remember such an address. To make it prettier, we often convert it to a hexadecimal and then split the hexadecimal into $$$8$$$ sections. Each section is a $$$4$$$-bit hexadecimal and we can remove its leading zero. So $$$x$$$ can be represented as 2001:470:f003:0:0:0:0:1.

This is still too long, so it's allowed to remove several consecutive sections of zeros and replace them with a double colon (::). RFC 5952 recommands not to use a double colon to denote an omitted single section of zeros so we should obey. Certainly, the double colon can be used only once in an address or the address would become ambigious. For example, $$$x$$$ can be abbreviated to 2001:470:f003::1.

Now you are given an 128-bit IPv6 address and you should output its abbreviation. If there are multiple legal abbreviations, output the shortest one with least remaining sections. If there are still multiple shortest abbreviations, output the lexicographically smallest one.

An Orz Panda student who has been training for $$$2.5$$$ years is trying to find a job. The interviewer has given him a $$$n \times n$$$ matrix $$$\mathbf{A}$$$ and $$$n$$$ positive integers $$$b_1, b_2, \cdots, b_n$$$. Then the Orz Panda is asked for the value of

$$$$$$\left(\int_{-\infty}^\infty dx_1 \int_{-\infty}^\infty dx_2 \cdots \int_{-\infty}^\infty dx_n \ [\forall k: 0 \leq y_k(\mathbf{x}) \leq b_k]\right)^2$$$$$$

Here $$$\mathbf{x} = (x_1, \cdots, x_n)^T$$$, and $$$y_k(\mathbf{x})$$$ is the $$$k$$$-th value of the vector $$$\mathbf{A} \mathbf{x}$$$. Can you help the Orz Panda to calculate this value, in order to to get the job?

To avoid floating-point errors, you should output the answer modulo $$$M = 1000000007$$$. It can be proved that if the answer is finite, it should be a rational. So it's possible to represent it as $$$u/d$$$, where $$$u$$$ and $$$d$$$ are two integers, and $$$gcd(u, d) = 1$$$. If the answer is finite, and $$$d^{-1} \mod M$$$ exists, output $$$u \cdot d^{-1} \mod M$$$. Otherwise output "Orz".