A boy, whose ID is smzzl, loves solving problems on Codeforces. Some day, he was solving the following problem:

Given a string $$$S$$$, find the lexicographical-smallest string $$$T$$$, whose lexicographical order is no smaller than $$$S$$$, the times each letter appears in $$$T$$$ are multiples of $$$k$$$, and $$$|S|=|T|$$$.

"The problem is too easy! I want a harder one!"

So, he modified the problem. He no longer requires the times each letter appears in $$$T$$$ to be a multiple of $$$k$$$. Instead, he wants them to be a factor of $$$k$$$ or 0.

The problem actually becomes harder, but not so much harder. Fall, the teammate of smzzl, solved it immediately! And now, Fall wants you to solve it, so he can check his answer.

Fall is playing a game about a war.

There are $$$n$$$ soldiers standing in a line. Some of them belong to the player, while others belong to the enemy. Due to the spies, the belonging of some of them is unknown. Now, as an artillery, the player may win this game under the following rules after identifying the belonging of each soldier:

Step 1: Choose a soldier which belongs to the player. There should be exactly two soldiers next to the chosen one, which means the chosen soldier should be neither at the beginning nor at the end of the line.

Step 2: Kill the soldiers next to the chosen one (the chosen one will remain alive).

Step 3: Repeat step 1 and step 2 until all the soldiers left belong to the same side (the player or the enemy).

The player wins if all the soldiers left belong to the player. Fall, as the player, wants to know the number of ways to identify the belonging of each soldier so that he can win.

However, soldiers may change their state (the player's troops, the enemies, or unknown). You need to calculate the answers after every change.

Fall wants to draw a perfect binary tree.

We first stipulate that all nodes in the tree with the same depth also have the same y-coordinate in the plane. Define nodes with the same depth to be nodes at the same level, then the perfect binary tree has four properties.

• It is a full binary tree.
• The difference between the y-coordinates of two nodes at each adjacent level is a constant.
• The difference between the x-coordinates of two adjacent nodes at the same level is constant.
• The x-coordinate of each node is the average of the x-coordinates of its sons.

Fall has drawn the root node and its left and right sons of this binary tree. Now Fall intends to draw a total of $$$k$$$ levels and cut the binary tree down and paste it on the wall afterwards, so he wants to know what is the area of the convex hull of all nodes of this perfect binary tree.

There were a lot of balls in the factory of Ball Illusion Technology(BIT). Link, a boy, went there to get some balls, but suddenly, he found that there were too many ways to get balls.

There are $$$2n$$$ buckets in the factory. Link may get $$$kx$$$ balls from the $$$2x-1^{th}$$$ bucket, where $$$k$$$ is a non-negtive integer. He may also get at most $$$x$$$ balls from the $$$2x^{th}$$$ bucket.

Link wanted to get $$$m$$$ balls, and he wondered how many ways there were to take out exactly $$$m$$$ balls. While Link is calculating the answer, he wants you to calculate it as well, and you should output the answer modulo $$$10^9+7$$$.

We often say that details can reflect the level of one's EQ. For example, at BIT, when students study in classrooms (such as A105 in the General Teaching Building) or on long tables in the library, it is often embarrassing and uncomfortable (and occasionally smelly) if another student suddenly sits next to them, which we call low EQ behavior.

Now, there is a long table containing $$$n$$$ seats, and the BIT students will choose their seats in the following way in order to avoid low EQ behavior as much as possible.

• If the whole table is empty, randomly choose a position to sit.
• Otherwise, choose a position whose shortest distance to other students is maximized. If there are more than one, randomly choose one of them with equal possibility.

When the farthest distance is $$$1$$$ (i.e., he will sit next to a classmate anyway), students will sit at a different table to avoid low EQ behavior, and then we will call the table full.

Now, Link wants to know the expected number of people seated in the table when the table is full.

"We are wasting time, let's go!"

"Terrorists win."

"Form up, let's go!"

"Terrorists win."

......

After being defeated several times, he was so angry that he decided to cheat. He used some tricks to make himself fly really high so that nobody could hurt him. He started to throw grenades, but he suddenly found that he had only 1 hp, which means he would die if the grenade hurt him. Now, Link wants to know the possibility that he will die.

Formally, there is a grenade with initial speed $$$v_0$$$ m/s and explode time $$$t$$$ s, which was thrown in a random direction. When the grenade explodes, it will hurt anyone whose distance to it is no more than $$$r$$$. Supposing that the grenade didn't touch anything before explosion, and the man didn't move after throwing the grenade, you should output the probability that the man will survive.

In order to check your answer precisely, you should output it modulo $$$10^9+7$$$.

Note1: This is a 3D game. In this game, the acceleration of gravity is $$$10$$$ $$$m/s^2$$$.

Note2: It can be proved that the answer can always be represented as $$$\frac{p}{q}$$$, where the greatest common factor between $$$p$$$ and $$$q$$$ is $$$1$$$. When outputting the answer modulo $$$M$$$, you should output such an integer $$$x$$$ that $$$0 \leq x \lt M$$$ and $$$ x \cdot q \equiv p (mod\ M) $$$.

Link has a function $$$f(x)$$$, where $$$x$$$ and $$$f(x)$$$ are both integers in $$$[1,n]$$$.

Let $$$f_n(x)=f(f_{n-1}(x))$$$ and $$$f_1(x) = f(x)$$$, he define the power of a number $$$x$$$ as: $$$$$$g(x) = \lim \limits_{n \to + \infty} \frac{1}{n} \sum_{i=1}^{n} f_i(x)$$$$$$

He wants to know whether $$$x$$$ has the same power for all $$$x \in [1,n]$$$.

Smzzl is going to make an AI for Greedy Snake. The game goes on xOy plane and there is no obstacles in the plane.

In this game, the snake takes $$$1$$$ unit of time to move forward for one unit of length. It also takes $$$1$$$ unit of time for the snake to rotate for 90 degrees. (The snake must rotate for the whole unit of time.) There is a food in the map initially. After the snake eat each food, the next food appears.

Smzzl certainly want the snake to eat the food as fast as possible, so he need to minimize the time when the snake eat each food. Please output a valid operate sequence.

A boy, whose ID is smzzl, is playing a game named Zig-Zag-Land(ZZL). This is a 2D battle royale game. When the game starts, you will spawn in a random place in the map, and your target is to move into the safe zone.

Given the border of the map and the border of the safe zone, he wants to know the shortest distance between the spawn point and the safe zone in the worst case.

It can be proved that the square of the answer is always rational. In order to check your answer precisely, you need to print the square of your answer modulo $$$10^9+7$$$. You may find the way to modulo a rational number in Problem F.

A boy, whose ID is smzzl, loves drinking Black Ice Tea(BIT), especially the tropical taste one.

The shop owner knows that, and she prepares a swimming pool so that there would be enough space for her to store BIT. When the boy knows that the owner prepared a swimming pool, he starts to drink in the swimming pool. While the owner is pouring BIT into the swimming pool, the boy is drinking it, too.

Assuming that there are $$$V$$$ liters of BIT in the swimming pool, the speed the owner pours BIT is $$$qV$$$ liters per second, and the speed the boy drinks BIT is $$$pV$$$ liters per second. Note that $$$V$$$ changes as the time goes.

Now, the owner wants to know whether the following statement is true:

For any $$$G \gt 0$$$, there exists a $$$T \gt 0$$$, for any $$$t \gt T$$$, the boy drinks more than $$$G$$$ liters of BIT after $$$t$$$ seconds.

Given an array $$$a$$$ of length $$$n$$$, for any array $$$b$$$ satisfying $$$1 \leq b_i \leq n$$$ and $$$b_1 \lt b_2 \lt \cdots \lt b_k$$$ ($$$k$$$ is the length of $$$b$$$, $$$k \geq 1$$$), calculate:

$$$$$$\prod_{b_1 \lt b_2 \lt \cdots \lt b_k} (a_{b_1}+a_{b_2}+\cdots+a_{b_k})$$$$$$

Recently, Yiwen is learning Assembly Language.

Since Yiwen is a genius in computer science, he proposed an extremely valuable technique called Basic Instruction Technology. Using this kind of technique, Yiwen can create numerous different instruction. Some of these instruction can be used to calculate some special eigenvalue of a string, such as $$$sqc$$$.

For a string $$$s$$$, let $$$s_i$$$ be the $$$i^{th}$$$ character of it.

Instruction sqc has 4 operands $$$s$$$, $$$l$$$, $$$r$$$ and $$$c$$$, where $$$s$$$ is a string, $$$1 \leq l \leq r \leq n$$$, $$$c$$$ is a character represented by ASCII value. $$$sqc(s,l,r,c)$$$ returns the number of character $$$c$$$ in substring $$$s_l \cdots s_r$$$.

Yiwen wants you to calculate following expression for the given string $$$s$$$: $$$$$$\sum_{c=97}^{122}\sum_{i=1}^{n}\sum_{j=i}^{n} sqc(s,i,j,c)^2$$$$$$

Note that the ASCII value of 'a' is $$$97$$$ and the ASCII value of 'z' is $$$122$$$.

The answer will probably be very huge, so just calculate the answer modulo $$$998244353$$$.