My Dearest Allie:

I couldn't sleep last night because I know that it's over between us. I'm not bitter anymore, because I know that what we had was real.

And if in some distant place in the future we see each other in our new lives, I'll smile at you with joy and remember how we spent a summer beneath the trees, learning from each other and growing in love. The best love is the kind that awakens the soul and makes us reach for more, that plants a fire in our hearts and brings peace to our minds. And that's what you've given me. That's what I'd hoped to give to you forever.

I love you. I'll be seeing you.

Through time passes, there is always someone we will never forget.

"Although there were millions of trees in the world, there was only one that The Little Prince took care of with his heart. And although there are countless people in the world, there is only one that I take care of with my heart." said Zayin to Ziyin with affection.

"Millions of trees? I may not agree with you. Just a tree could have millions of structure." answered Ziyin proudly, "Let's do the some math."

...

Thinking of the days they have happily spent together, Zayin can't help bursting into tears. Though Ziyin has been gone for a long time, Zayin still misses her every much.

He remembers it was a sunny afternoon when Ziyin and him were lying in the yard, resting beneath the shade of a tree, working on the number of nodes satisfying that if the tree is rooted by the node, the rooted tree is a rooted binary tree.

When times smoothes all sorrows, Zayin also forgets the answer of the problem. He only remember the structure of the tree. Maybe it's time for Zayin to let all memories about Ziyin go, but he still want to figure out the answer out of sentiment.

As Zayin's friend, you may want Zayin to get released as soon as possible, can you help him?

In short, given an unrooted tree, please calaculate how many nodes satisfying that if the tree is rooted by the node, the rooted tree is a rooted binary tree.

Given a set $$$S$$$ of first $$$N+1$$$ non-negative integers i.e. $$$S = \{0, 1, 2, ..., N\}$$$. Find number of ways of choosing a $$$K$$$ size subset of $$$S$$$ with the property that the XOR-sum of all chosen integers has exactly $$$B$$$ set bits in its binary representation (i.e. the bits that are equal to $$$1$$$). Since the answer can be large, output it modulo $$$998244353$$$.

Zayin have a number $$$x$$$ which initially is equal to $$$1$$$, a prime number $$$p$$$, and $$$n$$$ operations, where the $$$i$$$-th operation must be one of the followings:

• $$$x$$$:=$$$a_i$$$: assign the value $$$a_i$$$ to $$$x$$$
• $$$x$$$*=$$$a_i$$$: assign the value $$$(x\times a_i)\ modulo\ p$$$ to $$$x$$$

Zayin will perform the $$$n$$$ from left to right, for example, if $$$p=7$$$ and there are $$$3$$$ operation - $$$x$$$:=$$$1$$$, $$$x$$$:=$$$2$$$, $$$x$$$*=$$$3$$$ respectly, the value of $$$x$$$ is $$$6$$$ eventually.

But Ziyin, as the naughty girlfriend of Zayin, may shuffle the operations randomly. In spite of that, Zayin found that some values would never be introduced no matter how the operations is shuffled, for example, the value $$$0,4,5$$$ can't be calculated no matter how $$$x$$$:=$$$1$$$, $$$x$$$:=$$$2$$$, $$$x$$$*=$$$3$$$ is shuffled.

Zayin is curious about how many values between $$$0$$$ and $$$p-1$$$ (both inclusively) can't be calaculated, can you help him?

Zayin have learned how to compute the number of periods of a string recently.

As his girlfriend, Ziyin would like to give Zayin some strings and test whether he really learn the knowledge well. But Ziyin is too lazy to produce strings which are completely different, so she would firstly give Zayin a string, and ask him if she modify the $$$i$$$-th character of the string to #, what is the number of periods of the new string. (Note that Ziyin wouldn't really perform the modification)

It's really a big question for Zayin. Can you help him so that he would not lose face in front of his girlfriend?

Setsuna likes staying at home. No matter what happens at school, she has little interest and only wants to go home to play games. One day when she was back, she opened a rhythm game and found that her favorite event was helding.

For each round in this event, a player has to play two different songs which are randomly chosen by system. There are totally $$$n$$$ songs in the system, and Setsuna is able to gain a score of $$$a_i$$$ if she plays the $$$i$$$-th song. The score of a round is the sum of scores of the two songs.

Initially the system presents two different songs which are randomly selected with equal probability. If the player is unsatisfied with the result, he can ask the system to reselect (of course randomly). But there are only $$$k$$$ opportunities of reselecting in total.

Setsuna had many questions. Firstly, she wanted to know her expected score under optimal decision. Secondly, she assumpted $$$Q$$$ cases, each of which was as the form of "the system selected the $$$x$$$-th song and the $$$y$$$-th song currently, and there were $$$c$$$ chances of reselecting left", and you need to answer whether she should accept the result, or decide to reselect, or both are OK if the difference of expected scores of these two choices under optimal decision is less or equal than $$$10^{-4}$$$.

Zayin and Ziyin are playing a game with $$$n$$$ piles of stones, where the $$$i$$$-th pile has $$$a_i$$$ stones for each $$$1\le i\le n$$$. Zayin and Ziyin play in turn, with Zayin going first.

• First, Zayin chooses a positive integer $$$s_1$$$ and some piles with at least $$$s_1$$$ stones, removes $$$s_1$$$ stones from each of the chosen piles.
• Then Ziyin chooses a positive integer $$$s_2$$$ such that $$$s_2$$$ divides $$$s_1$$$ and some piles with at least $$$s_2$$$ stones, removes $$$s_2$$$ stones from each of the chosen piles.
• Then Zayin chooses a positive integer $$$s_3$$$ such that $$$s_3$$$ divides $$$s_2$$$ and some piles with at least $$$s_3$$$ stones, removes $$$s_3$$$ stones from each of the chosen piles.
• ...
• In general, $$$s_i$$$, the number of stones removed in each of the chosen piles in turn $$$i$$$, must divide $$$s_{i-1}$$$ for $$$i \gt 1$$$.

The one who is unable to remove stones in his turn lose.

Compute the number of strategies Zayin can make in his first turn in order to guarantee a win no matter what choices Ziyin makes.

Two strategies are considered to be different if they remove a different number of stones or they remove stones from different set of piles.

During your participation in this competition, Shinyruo is preparing to order KFC for the offline competition next week.

There are $$$n$$$ kinds of foods in KFC, and he plans to order $$$a_i$$$ number of the $$$i$$$-th food for every $$$i \in [1,n]$$$. Due to shortage of manpower, the total number of all kinds of foods is no larger than $$$10^5$$$.

After the competition, he will hand all the KFC out to $$$k$$$ teams. Each team can get different kinds of foods but for each kind it can get one at most.

Now Shinyruo wants to know the number of ways to hand the desserts out. As he doesn't know the number of participating teams, you need to calculate the answers for $$$k=1,2,\cdots,m$$$.

As the answer can be large, print it modulo $$$998244353$$$.

Country X is a prosperous free-trade country, which has $$$n$$$ cities connected by $$$n-1$$$ bidirectional roads. Although country X has been very stable, businessmen are generally very sensitive to the safety of cities. They hope country X can strengthen public security forces to ensure the safety of cities.

In addition, businessmen are also concerned about the safety of the surrounding areas. Therefore, if the security force in a city is strengthened, but the security force in the nearby cities are not strengthened, they will still be worried about the threat in nearby cities.

Formally, to strengthen the security force in city $$$i$$$, a cost of $$$w_i$$$ should be paid. Such effort is not in vain, as more businessmen will be attracted and country X will benefit from it. If every city with a distance from city $$$i$$$ less or equal to $$$p$$$ is strengthened, the city $$$i$$$ will gain $$$v_p$$$ more income than before. (if more than one $$$p$$$ satisfy the condition, only the maximum one is considered.)

Now you, as the country's officer, are appointed to deal with this problem. Your goal is to get the maximum benefit (the increased income minus the cost of strengthening the security force).

Moon has learned the Hasse Diagram in his math course. Therefore, he draws an undirected graph with $$$n$$$ nodes indexed $$$1,2,\cdots,n$$$ and adds some edges between node $$$x$$$ and node $$$y$$$ if $$$x|y$$$ and $$$\frac{y}{x}$$$ is a prime while the weight of the edge is $$$\frac{y}{x}$$$.

Moon wants to know the value of $$$\sum_{i=1}^{n}\sum_{j=1}^{n}dis(i,j)$$$, where $$$dis(x,y)$$$ means the shortest distance between node $$$x$$$ and node $$$y$$$. Since the answer will be very large, you should print the answer modulo $$$10^9+7$$$.

Mr. JR is an expert billiard player who has won the championship of BBPC (Billiard Ball Playing Contest). Nowadays, Mr. JR is tired of the ordinary rectangular billiards table and has great interest in the circular billiards table. Specifically, he is thinking about the following problem.

Mr. JR puts a white ball on the edge of the circular billiard table, and uses the club to hit the white ball at the angle of $$$\beta\ (0 \lt \beta \lt 90)$$$. He wants to know how many times the white ball will collide with the edge of the circular billiard table before it returns to the origin for the first time.

The collision between the ball and the table conforms to the law of mechanics, that is, relative to the tangent of the collision point on the table edge, the incident angle $$$\alpha_1$$$ is equal to the exit angle $$$\alpha_2$$$ (as shown in figure (b)). And there will be no energy loss in the collision (that means the friction between the ball and the table is not considered, as shown in figure (a)).

This problem is too difficult for Mr. JR. Can you help him?

Even though they are tiny now, they will be shiny shooting stars someday.

It is every newbie's dream to be a grandmaster in algorithm contests, including Zayin. So it is your task to encourage him.

Zayin is solving a problem. He is given an integer $$$n$$$ where $$$n$$$ is an odd prime. Simultaneously there is an undirected graph with $$$n-1$$$ vertexes, labeled from $$$1$$$ to $$$n-1$$$, and a parameter $$$a\in[1,n)$$$. For every vertex $$$i$$$, Zayin has to assign an edge for it from one of the two options:

• add an edge between $$$i$$$ and $$$\frac ia \bmod n$$$. The time cost of it is $$$1$$$ due to the calculation of multiplying $$$a^{-1} \bmod n$$$.
• add an edge between $$$i$$$ and $$$\frac ai \bmod n$$$. The time cost of it is $$$\lceil \log_2 n \rceil$$$ due to the calculation of the inverse of $$$i$$$.

$$$a$$$ is not shown to Zayin until he has decided the way to assign edges. After that, Zayin runs his naive algorithm on the graph. For every connected component with size $$$s$$$, the time cost is $$$s^2$$$.

If the total time cost is less or equal than $$$12n$$$, the algorithm will be accepted.

You are to help Zayin in the following ways:

1. You give him an oracle sequence $$$oracle_1,\cdots,oracle_{n-1}$$$ where each $$$oracle_i \in \{0,1\}$$$ represents the option to choose for vertex $$$i$$$, i.e. if $$$oracle_i=0$$$, he links $$$i$$$ and $$$\frac ia \bmod n$$$, otherwise he links $$$i$$$ and $$$\frac ai \bmod n$$$.
2. Then the judge will randomly generate 20 parameters $$$a_1,\cdots,a_{20}$$$. The algorithm passes the test case if it is accepted on some $$$a_i$$$ of them. Notice that Zayin uses the same oracle for every $$$a$$$.

There are $$$n$$$ lovely children standing in a row, numbered from $$$1$$$ to $$$n$$$ from left to right. Their positions are also numbered from $$$1$$$ to $$$n$$$ from left to right. Initially, no one has shaken hands with others. Their teacher is playing a game. In each turn, the teacher chooses two adjacent children and let them shake hands with each other. After shaking hands, the two children will swap their positions. After $$$m$$$ turns, the teacher asks you a question: can you choose some children as many as possible such that every pair of chosen children has shaken hands with each other?

In the platypus kingdom, there is a popular game throughout the kingdom–Hearthstone. Hearthstone consists of eight players in each game, and only one of them wins. Due to the difficulty of winning, many platypuses share their best moments of playing the game via live streams. Recently, a Bible "810975" spread.

"810975, why can't newcomers understand?!"

"810975, why are you the only one who doesn't understand?"

...

Recently, Zayin is reciting the Bible 810975 every day. He also continues to explain to his friends the specific meaning of 810975: On August 10, the Platypus King played 9 games and won 7 times, including a 5-game winning streak. But today, there comes a new platypus, Ziyin, who doesn't know the meaning of 810975. So Zayin excitedly explains to him. However, Ziyin has a question, "How many situations are there if I play $$$n$$$ games and win $$$m$$$ games, and the longest winning streak is $$$k$$$?"

If we use 1 to represent victory and 0 to represent defeat, any string consisting of 0 and 1 of length $$$n$$$ can represent a situation of an $$$n$$$-round game. Two situations are different if and only if the two 01 strings are different.