$$$112358$$$ is a team from Hunan University that participated in this year's ICPC WuHan station.

Why this name? Because zmy is very fond of playing a game called $$$112358$$$.

The rules of the game are as follows:

There are a total of 16 squares, and each move can shift the tiles up, down, left, or right. If two adjacent numbers satisfy the condition that they are consecutive terms in the $$$\bf{Fibonacci\ sequence}^\dagger$$$, they will merge into their sum, and the score increases by the value of the new number.

After each move, you can either add a new number $$$1$$$, or not add at all. Note that the newly added $$$1$$$ is not included in the total score.

Now, given a current board state of the $$$112358$$$ game, you are asked to output the current score modulo 998244353.

$$$^\dagger$$$ The Fibonacci sequence is defined as

$$$$$$F_1 = 1,\ \ \ F_2 = 1,\ \ \ F_i = F_{i-1} + F_{i-2} \ \text{for all } i \ge 3.$$$$$$

The first $$$10$$$ terms are $$$[1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55].$$$

Reimu and Marisa are playing a card game, described as follows:

There are $$$2n$$$ cards in total, with numbers $$$1$$$ to $$$n$$$ each appearing twice. Each player holds $$$n$$$ cards. They take turns playing one card, with Reimu going first.

After a player plays a card, if there are at least $$$2$$$ cards in the pile, and the top card of the pile is the same as the bottom card of the pile, then that player takes all the cards from the pile and gets one point.

Now, given Reimu's card sequence, Marisa wants to minimize Reimu's score. Under optimal strategy, what is the minimum score Reimu can get?

A caterpillar is a special type of tree.

First, it satisfies the basic property of a tree: it is a connected graph with $$$n$$$ vertices and $$$n-1$$$ edges. Then, the caterpillar can be divided into four parts: head, body, tail, and feet.

Among them, the head is vertex $$$1$$$, the body is a chain length of $$$len$$$ connected by vertices $$$2,3,\dots,len+1$$$ in order, the tail is vertex $$$len+2$$$, and the feet are other vertices directly connected to the body.

The head connects to the body, and the body connects to the tail. So vertices $$$1$$$ to $$$len+2$$$ are connected into a chain in order (There is a caterpillar with $$$n=14$$$ and $$$len=3$$$).

Now, you are given a caterpillar. You need to assign a weight to each vertex, which must be a permutation of $$$1$$$ to $$$n$$$. The edge weight is defined as the absolute difference between the weights of the two vertices it connects.

You need to construct a vertex weight scheme such that the edge weights is a permutation of $$$1$$$ to $$$n-1$$$.

Evil Neuro loves cubes!

Inside the $$$n \times n \times n$$$ electronic toy chest, Evil controls cubes, each occupying a $$$1 \times 1 \times 1$$$ coordinate within the grid. Since the cubes are digital, they can defy gravity and float in mid-air. That is to say, Evil can place them anywhere inside the chest.

Evil wants the chest to look completely packed. To pull it off, the arrangement must be filled from every angle. Whether viewed from the front, the side, or above, the chest must appear as a solid $$$n \times n$$$ block, with no space left.

Unfortunately, Evil has a limited supply of cubes. She asks you to help her do this using the minimum number of cubes.

Alice and Bob are playing a classic game known as "Dots and Boxes".

The game is played on a rectangular grid of size $$$n \times m$$$. The game proceeds as follows:

• Alice and Bob take turns adding a single horizontal or vertical edge between two adjacent unconnected cells. Alice goes first.
• If placing an edge completes a $$$1 \times 1$$$ cell (i.e., the cell is surrounded by 4 edges), the current player scores $$$1$$$ point and must take another turn immediately. The player continues to take turns as long as they complete a cell.
• If the placed edge does not complete any cell, the turn ends, and the other player begins their turn.
• The game ends when all edges have been drawn and all cells are completed. The player with the higher score wins.

Alice and Bob have paused the game in a specific state. Currently, every single cell $$$(i, j)$$$ in the grid is surrounded by exactly 2 drawn edges and 2 empty edges. Since no cells are fully completed yet, the current score is $$$0-0$$$.

Given this board state, Alice takes the next move. Determine whether Alice has a winning strategy regardless of how Bob plays. Alice wins if Alice's score is strictly greater than Bob's score at the end of the game.

In the beautiful Sweet Apple Acres, Applejack is facing her busiest harvest season of the year. She has sorted the harvested apples into $$$n$$$ quality grades (numbered from $$$1$$$ to $$$n$$$). Specifically, she has harvested exactly $$$a_i$$$ apples of grade $$$i$$$.

However, the energetic Rainbow Dash decided to "help" out. She attempted to clear the fallen leaves quickly using her Sonic Rainboom. Unfortunately, she used a bit too much force, and a gust of wind blew away exactly $$$k$$$ apples, causing them to disappear.

As the Element of Honesty, Applejack didn't blame Rainbow Dash. However, she is now facing a mathematical puzzle. Among all possible ways to remove exactly $$$k$$$ apples, there are various outcomes for the "mode" (the most frequent grade) of the remaining pile. She wants to find the maximum possible grade that can serve as a mode in any such outcome.

The problem setter, Mofusigil, who is secretly snacking on apples nearby, wipes his mouth and throws this problem to you.

Joseph's game is like this: $$$N$$$ people are arranged in a circle clockwise, and each person's number is from $$$1$$$ to $$$N$$$. Starting from No. 1, one person is eliminated by $$$M$$$ people clockwise, leaving the last person as the winner, whose number is the lucky number.

Given $$$N$$$ and $$$M$$$, find the lucky number.

ACM is the world's most influential collegiate programming competition, known as the "Olympics of Programming," requiring teams to solve complex algorithmic problems efficiently within a limited time.

In the ACM competition, the rules for award allocation stipulate that gold, silver, and bronze medals are awarded to the top $$$10\%\ ,20\%$$$, and $$$30\%$$$ of valid teams, respectively, with rounding up applied.

Now given the number of valid teams $$$n$$$, please answer how many teams get gold, silver, and bronze medals, respectively.

Mofusigil decides to test the wit of his old friend, Caiwen.

Mofusigil starts with a hidden original string of length $$$n$$$. He then performs exactly $$$m$$$ operations on it. In each operation, he selects a random position in the string and replaces the character at that position with a different lowercase English letter.

It is important to note that:

• The same position can be modified multiple times.
• The character used for replacement must always be different from the character currently at that position (immediately before the replacement).
• The string consists only of lowercase English letters.

After performing these $$$m$$$ operations, Mofusigil shows Caiwen the final result string and asks: "Based on this final string, how many different original strings could I have started with?"

Mofusigil expected Caiwen to solve this instantly, but Caiwen stared at the string in total confusion. Seeing his friend's struggle, Mofusigil decided to go easy on him and guaranteed that the number of operations $$$m$$$ is very small: $$$m \le 2$$$.

Unfortunately, even with this simplification, Caiwen is completely stumped. Not wanting to lose face in front of Mofusigil, Caiwen has secretly asked for your help.

Neuro-sama has a single banknote with a value of $$$n$$$ dollars. She can repeatedly apply the following operation:

• Take a banknote with a value $$$t$$$ such that $$$t \ge k$$$, and replace it with $$$k+1$$$ new banknotes: $$$k$$$ banknotes each with value $$$\lfloor t/k \rfloor$$$, and one banknote with value $$$t \bmod k$$$.

Neuro keeps applying this operation until all banknotes have a value less than $$$k$$$. Now she is interested in the number of $$$0$$$-dollar banknotes that she will have at the end. As Neuro-sama's fan, please find the answer for her.

You will be given $$$q$$$ independent queries. For each query, output the number of $$$0$$$-dollar banknotes obtained at the end, modulo $$$10^9+7$$$.

$$$~\\$$$

Neuro-sama and Evil are planning to build houses on a tree. The tree has $$$n$$$ nodes and $$$n-1$$$ edges. Each node is capable of hosting exactly one room, and together these rooms will form the house.

Evil, always overflowing with ideas, has drafted $$$q$$$ different construction plans. In each plan, she selects a set of nodes $$$S$$$, and places one room on every node in $$$S$$$. However, her sister Neuro has a rather strict aesthetic sense. For her, a construction plan is considered elegant only if all rooms form a single connected area — that is, for any two nodes $$$u, v \in S$$$, there exists a path between $$$u$$$ and $$$v$$$ entirely within $$$S$$$.

To keep the peace (and prevent Evil from storming off to draft even stranger structures), Neuro asks for your help: for each of the $$$q$$$ plans, determine whether the plan is elegant.

You are given two integers $$$n$$$ and $$$p$$$, where $$$p$$$ is a prime number.

Find a permutation $$$a_1,a_2,\dots,a_n$$$ of the integers from $$$1$$$ to $$$n$$$ (each number appears exactly once), such that for every index $$$i$$$ with $$$2\le i\le n-1$$$, the following holds:

• $$$a_{i-1}\cdot a_i\bmod p \ne a_i\cdot a_{i+1}\bmod p$$$.

If such a permutation exists, output any valid permutation; otherwise, output $$$-1$$$.

Ris, the administrator of the Prism Area, has regained her memories and power. However, to reconstruct the world that was once on the verge of collapse, she needs to stabilize the "Kaleidoscope" — the core system that connects all seven worlds.

The Kaleidoscope is built from $$$n$$$ memory fragments. Each fragment $$$i$$$ possesses a unique energy signature represented by a non-negative integer $$$a_i$$$.

In the world of 7sRef, connections between fragments are formed based on "resonance." Two distinct fragments $$$i$$$ and $$$j$$$ are connected by a bond (an undirected edge) if and only if their energy signatures share at least one common "color". Mathematically, this means the bitwise AND of their values is non-zero: $$$$$$a_i \ \& \ a_j \neq 0$$$$$$

To activate the Kaleidoscope, Acid (Ris's partner) needs to find a closed loop of resonance within these fragments. Specifically, she needs to find the smallest cycle in this graph formed by the fragments and their connections.

Mofusigil decided to help Acid calculate the length of the shortest cycle (the number of edges in the cycle). If no cycle exists in the graph, output $$$-1$$$. However, Mofusigil's ability is limited and he could not calculate the result, so this important task is handed over to you.