Professor Oak is preparing a problem for his students. The problem consists in counting the number of ways of placing $$$n$$$ rooks on an $$$n \times n$$$ chessboard such that no rook is threatening another rook (that is, no two rooks are in the same column or in the same row).

However, this problem is too easy, so he has decided to add a twist. He only wants you to count the number of solutions in which there are exactly $$$k$$$ pairs of rooks that are diagonally adjacent (that is, they are in neighboring columns and in neighboring rows). Can you solve it?

Output your answer modulo $$$10^9 + 7$$$.

A permutation $$$a_0, a_1, \ldots, a_{n - 1}$$$ of $$$0, 1, \ldots, n - 1$$$ is said to be beautiful if the sequence $$$b_0, \ldots, b_{n - 1}$$$ defined as $$$b_i = |a_i - i|$$$ is also a permutation of $$$0, \ldots, n - 1$$$.

Given $$$n$$$, construct a beautiful permutation of $$$n$$$ elements or determine that it does not exist.

Let $$$G$$$ and $$$H$$$ be two weighted undirected simple graphs. We define the cartesian product of the two graphs, $$$G \square H$$$, as the graph whose vertex set is the cartesian set product of the vertex sets of the two graphs $$$V(G) \times V(H)$$$ and in which there is an edge between vertices $$$(u_1, v_1)$$$ and $$$(u_2, v_2)$$$ if and only if:

• $$$v_1 = v_2$$$ and there is an edge $$$(u_1, u_2)$$$ in $$$G$$$. In this case, the edge$$$((u_1, v_1), (u_2, v_2))$$$ in $$$G \square H$$$ has the same weight as the edge $$$(u_1, u_2)$$$ in $$$G$$$.
• or $$$u_1 = u_2$$$ and there is an edge $$$(v_1, v_2)$$$ in $$$H$$$. In this case, the edge$$$((u_1, v_1), (u_2, v_2))$$$ in $$$G \square H$$$ has the same weight as the edge $$$(v_1, v_2)$$$ in $$$H$$$.

You are given two connected graphs $$$G$$$ and $$$H$$$. Compute the total weight of the minimum spanning tree of $$$G \square H$$$.

Elater is a great magician. His most famous show is "Elater's Super Spectacular Display of Springs". The show consists in the following:

There are $$$n$$$ elastic springs in a line attached to the ceiling. Spring $$$i$$$ is attached at height $$$h_i$$$ and has a stiffness constant $$$k_i$$$. If we attach a weight of mass $$$w$$$ to the lower end of the $$$i$$$-th spring, the weight will descend to a height $$$H$$$ given by the formula:

$$$$$$H = h_i - \frac{w}{k_i}\text{.}$$$$$$

Elater will take questions from people in the audience. When asked about a positive integer $$$w$$$, Elater will be able to pick the spring which, if a weight of mass $$$w$$$ is attached to its lower end, will descend to a height lower (closer to the floor) than all the other springs (in case of a tie, he will be able to pick one of the springs with the lowest descend height). To accomplish such an amazing feat, Elater has the help of his dear assistant, Hooke.

Before the show, Hooke has some time to do measurements on the springs. He can not directly measure the values of $$$h_i$$$ and $$$k_i$$$, but he can choose two springs $$$a$$$ and $$$b$$$ and a mass $$$w$$$, try attaching a weight of mass $$$w$$$ to the two springs, and see which of them goes closer to the floor with that weight. Before the show, he has time to do up to $$$20\,000$$$ such measurements. Also, after each question, Elater can distract the audience for a while, so that Hooke can do up to $$$20$$$ more measurements before inconspicuously whispering the answer to Elater.

Can you help Hooke make the show successful? Assume that the springs are attached high enough, and the masses are small enough, so that the weights never reach the floor during any possible measurement. Also note that the weights are removed after each measurement.

First, you must read a single line with the integer $$$n$$$ ($$$2 \leq n \leq 500$$$) from the input.

To make a measurement, you must print a single line formatted as "? $$$a$$$ $$$b$$$ $$$w$$$", where $$$a$$$ and $$$b$$$ ($$$0 \leq a, b \leq n - 1$$$) are the indices of the two springs you want to use, and $$$w$$$ ($$$1 \leq w \leq 10^5$$$) is the integer weight you want to put in both springs. After that, you must read from the input a single line with the answer, which will be the word "FIRST" if spring $$$a$$$ reaches lower height, "SECOND" if spring $$$b$$$ reaches lower height, or "EQUAL" if both reach the same height.

During the first stage, you can make at most $$$20\,000$$$ measurements. After doing all the measurements of the first stage, print a single line with a single character "!". After that, you will be given one or more questions.

Each question is given on a single line formatted as "QUESTION $$$w$$$" where $$$w$$$ is the integer weight Elater is asked about ($$$1 \leq w \leq 10^5$$$). After reading each question, you can do at most $$$20$$$ measurements, in the same format as in the first stage. Once you have done the measurements, output a single line formatted as "! $$$i$$$", where $$$i$$$ ($$$0 \le i \le n - 1$$$) is the index of the spring that is the answer to the question. If there are multiple springs that reach the same minimum height, you may print any of them.

After all questions, instead of the next one, you will get a single line consisting of the word "FINISH". It means there are no more questions and your program must finish. The total number of questions will be at least $$$1$$$ and at most $$$1000$$$.

Don't forget to flush the output after printing each line!

In each test, the values of $$$h_i$$$, $$$k_i$$$, and the questions are all fixed in advance.

You are given an array with $$$n$$$ pairwise different values: $$$A = [a_0, a_1, \dots, a_{n-1}]$$$. We define the sorted subarray of $$$A$$$ starting at $$$l$$$ and ending at $$$r$$$ as the array that we obtain after sorting $$$[a_l, a_{l+1}, \dots, a_r]$$$. For example, if we are given the array $$$[0,2,14,6,8,10]$$$, the sorted subarray starting at $$$1$$$ and ending at $$$4$$$ would be the array that we would get after sorting $$$[2,14,6,8]$$$, that is, the array $$$[2,6,8,14]$$$.

You are given $$$q$$$ queries, each one consists of two integers, $$$l$$$ and $$$r$$$. For each query, print the sum of the values in the even positions of the sorted subarray of $$$A$$$ starting at $$$l$$$ and ending at $$$r$$$. Here, we assume that all arrays are indexed starting from $$$0$$$.

For example, consider the array $$$[0,2,14,6,8,10]$$$ and the query $$$(1,4)$$$. The subarray starting at $$$1$$$ and ending at $$$4$$$ is just the array $$$[2,14,6,8]$$$. Thus, the sorted subarray starting at $$$1$$$ and ending at $$$4$$$ is the array $$$[2,6,8,14]$$$. Now we have to sum the values in even positions, that is, $$$2+8 = 10$$$.

Print the answers modulo $$$10^9 + 7$$$.

Let $$$p_0, p_1, \dots, p_{n-1}$$$ be $$$n$$$ points in the plane. We say that two points are friends if one can draw a circle that contains both points in its interior and all the other $$$n-2$$$ points in its exterior. Print the indices of the points that are friends with $$$p_0$$$.

It is guaranteed that there is no circumference containing $$$p_0$$$ and three or more other points. It is also guaranteed that there is no line containing $$$p_0$$$ and two or more other points.

Some friends, numbered from $$$0$$$ to $$$m-1$$$, are playing a game. There are cards of $$$c$$$ different colors, where colors are numbered from $$$0$$$ to $$$c-1$$$. Each card of color $$$i$$$ has a fixed value $$$p_i$$$. At the beginning of the game, each player chooses a certain amount of cards, without taking more than one card of the same color (though different friends may choose cards of the same color). We define the score of a deck as the GCD (greatest common divisor) of the values of its cards. Notice that an empty deck has a score of $$$0$$$ points. The game will be played on an undirected graph which is a tree consisting of $$$n$$$ nodes, numbered from $$$0$$$ to $$$n-1$$$. Each node $$$v$$$ contains a card with color $$$c_v$$$, and different nodes may have cards of the same color.

The game has $$$m$$$ rounds. In round $$$i$$$, the $$$i$$$-th friend gets to play. First, he chooses two different vertices $$$v$$$ and $$$u$$$. Then, for each node $$$v_i$$$ on the path from $$$v$$$ to $$$u$$$ (including $$$v$$$ and $$$u$$$), each player (including himself) draws a card of color $$$c_{v_i}$$$. If they already had a card of color $$$c_{v_i}$$$, they will discard both cards. After doing this, player $$$i$$$ gets as many points as the sum of the points of each player's deck (including himself). Finally, he chooses a node of the graph and draws a new card from the pile. Then he changes the node's card for the card he has just drawn (and discards the old card), ending his round.

Given the information of each round, print how many points each friend will have at the end of the game modulo $$$10^9 + 7$$$.

Score in chess tournaments is a controversial topic. Abel likes the classical system: 2 points per win and 1 point per draw. Bolzano prefers the football way: 3 points per win and 1 point per draw. But Cardano doesn't like either way and has his own system to declare a winner. We define the graph of the tournament as the graph where each node represents a player and an edge goes from player $$$v$$$ to player $$$u$$$ if player $$$v$$$ won at least one game against player $$$u$$$. Then Cardano states that a player $$$v$$$ wins the tournament only if in the graph of the tournament there is a path from $$$v$$$ to everyone else and there is none from any other player to $$$v$$$.

Recently, there has been a chess tournament of $$$n$$$ players, numbered from $$$0$$$ to $$$n-1$$$. The only information we have is the number of points of each player according to Abel's and Bolzano's criteria. Each player might have played any number of times with any other player. Determine if it is possible that player $$$0$$$ won the tournament according to Cardano's criteria.

We say that an integer $$$n \geq 1$$$ is joyful if, by concatenating the digits $$$25$$$ to the right of $$$n$$$, we get a perfect square. For example, $$$2$$$ is a joyful number (as $$$225 = 15^2$$$) but $$$3$$$ is not (as $$$325$$$ is not a perfect square).

Given an integer $$$k$$$ such that $$$1 \leq k \leq 10^9$$$, count the number of distinct prime factors of the $$$k$$$-th joyful number.

Given a graph, we say it is Königsbergsy if there is a simple path that goes through all of its bridges. Here, a bridge is an edge that disconnects the graph when removed. And recall that a simple path is a path that visits each vertex at most once.

Given a graph $$$G$$$, we want to add some edges to it to make it Königsbergsy. (You may add more than one edge between the same pair of vertices). Determine the maximum number of bridges that the resulting graph can have.

We have a grid of height $$$3$$$ and width $$$n$$$, as well as pieces that occupy $$$3$$$ adjacent cells. Given $$$n$$$, determine the number of ways to fill the grid so that each cell is covered by exactly one piece and no piece sticks out of the grid. Here there is an example of a way to fill a grid of width $$$4$$$:

Notice that any piece will be a rotation of one of the pieces of this example. Find the answers modulo $$$10^9 + 7$$$.