In the future several years, you will surely remember that you once participated in a special China Collegiate Programming Contest. Due to COVID-19, all parties had paid a lot of effort to eventually hold a rare online programming contest. As a problem writer, I would also like to express my sincere gratitude to the organizing committee, all the contestants and others who have worked hard in this process. I also sincerely wish you good results in this special contest and a special and sweat memory in the future.

Maybe several years later, you may recall that ...

Once there was a mobile game, where there was a virtual currency called coupon that could only be purchased by RMB. Kelo found that relying on his liver alone cannot make him stronger, so he decided to purchase some coupons. When he opened the recharge page, he found that this game had seven recharge columns, and was holding an activity called "First Recharge Reward". If it was the first time a recharge column was chosen, some additional coupons would be given to the player as a reward. A player might receive several rewards if he chose several different recharge columns. A column could be chosen for arbitrary times, but there would be no additional reward except for the first time it was chosen. Here is a table describing the price, amount of coupons in normal case and additional first recharge rewards of each column.

$$$$$$\begin{array}{|c|c|c|} \hline \text{Price (RMB yuan)} & \text{Normal amount (coupons)} & \text{First recharge reward (coupons)} \\ \hline 1 & 10 & 8 \\ \hline 6 & 60 & 18 \\ \hline 28 & 280 & 28 \\ \hline 88 & 880 & 58 \\ \hline 198 & 1980 & 128 \\ \hline 328 & 3280 & 198 \\ \hline 648 & 6480 & 388 \\ \hline \end{array}$$$$$$

Kelo had recently earned $$$n$$$ yuan by writing problems for China Collegiate Programming Contest. He decided to recharge all these $$$n$$$ yuan to the game, and hoped to get as many coupons as possible with these hard-earned money.

Once there was a hare, who was addicted to sleeping. The hare lived in a town, where there were also $$$n$$$ tortoises living in a row on a street, numbered from $$$1$$$ to $$$n$$$.

The hare could run much faster than the tortoises, so he often challenged the tortoises $$$m$$$-meter run. During such a race, when the hare was just before the finish line, the $$$i$$$-th tortoises could only run $$$a_i$$$ meters.

On a race day, the hare would pick an interval, maybe $$$[l, r]$$$. The tortoises numbered between $$$l$$$ and $$$r$$$ (inclusive), together with the hare, would compete in an $$$m$$$-meter race. Just before the the finish line, the hare would sleep for a while, as he led the race so much.

The hare had trained an ability during his long-term sleepiness, which was to curse $$$k$$$ tortoises every second when sleeping. The ability was available as soon as he fell asleep. Any cursed tortoise would be trapped in place for a second when cursed. One tortoise might be cursed multiple times. As the hare had no ability to think during sleep, he simply chose the $$$k$$$ tortoises closest to the finish line when applying his cursing ability.

After the hare fell asleep, due to the anger caused by the leader sleeping and the companion being trapped, all tortoises not trapped began to run as fast as $$$1$$$ meter per second.

In order to win the game, if the hare could not trap all the tortoises that were only one meter away from the finish line at some moment, he must wake up and cross the finish line immediately.

The hare wondered how many seconds he could sleep during each race, and asked you for help.

However, the problem was not that easy. On every day when there was no race, the $$$m$$$-meter running speed of one of the turtles will increase due to diligent exercise (or maybe decrease due to lack of exercise). Specifically, after that day, the tortoise numbered $$$u$$$ could run $$$v$$$ meters before the hare was just before the finish line. Note that his running speed might be changed again in the future.

Now can you still tell the hare exactly how many seconds he could sleep in each race?

Once there was a spiritual guy, who wanted to meet his best friend as soon as possible. Both he and his friend were on an Euclidean plane. He started his trip from $$$(0, 0)$$$, and his friend was located at $$$(L, 0)$$$.

If everything had been normal, he would reach his destination by walking $$$L$$$ meters, straight from $$$(0, 0)$$$ to $$$(L, 0)$$$. However, the region around was influenced by a mysterious force, which might be blamed on the $$$n$$$ magic towers around.

Every midnight, three towers were chosen by the mysterious force. High walls would appear on the boundary of the triangle formed by them as vertices, and would stay there until the next midnight. The walls were high enough to block sight, causing the spiritual guy unable to learn what was behind the wall. In other words, if the spiritual guy could only see one wall, any tower blocked by the wall, from his perspective, might be chosen as the remaining third tower. The spiritual guy travelled so fast that he could arrive where his friend were within one day. Therefore, you may assume the $$$3$$$ towers chosen remained unchanged during his trip. While travelling, he could gradually learn about the unknown area from his new perspective. Fortunately, he had so good a memory and a sense of direction that he knew where the $$$n$$$ towers and his destination were even if they were blocked by the wall, and could remember any situation as long as he was once able to see it. The spiritual guy was a pessimist, and would choose the shortest strategy in the worst case.

Example: The spiritual guy knew where the three grey towers and his destination were, but could not determine which one of the three grey towers was chosen when he set off.

If the spiritual guy could see all three chosen towers when departing, choosing a shortest path was no difficulty to him, so he came to you to verify his strategy where he could only see two chosen towers when he set off. He had designed several situations, and you are expected to tell him how much distance he needed to travel in the worst case, so that he could check his own answer.

Once there was a mathematician, who was obsessed with meaningless number sequences. Here is one of them.

$$$$$$a_n = \begin{cases} 1, & n = 0 \\ c \cdot \max\limits_{0 \leq i \lt n} a_{n \operatorname{\&} i}, & \text{otherwise} \end{cases},$$$$$$ where $$$\operatorname{\&}$$$ denotes the bitwise AND operation.

As a mathematician, he could easily tell what $$$a_n$$$ was for any $$$n$$$, but he wanted to test you. You are required to tell him

$$$$$$\left( \sum\limits_{i=0}^n a_i \right) \bmod (10^9+7)$$$$$$

to convince him that you have a deep understanding of this (although meaningless) sequence.

Once there was a highly anticipated e-sports championship, the 2020 League of Legends World Championship, where DWG defeated SN 3 to 1 in the finals.

Even though Oscar is a player of the game Defense of Valor League (DoVL) — a recently developed MOBA game, he could also felt the excitement of the finals, especially when the player SN Bin took the extraordinary PENTA KILL using the champion Fiora.

While watching the final games, he noticed that two teams always picked the red side when they were able to choose to act as the blue team or the red team. One possible explanation for such phenomenon may be that the red team holds the last pick, or Counter Pick, that may help team choose one good hero countering the opponent's lineup. He fell into deep thought: in the ban pick phase of the game, how much advantage or disadvantage does the blue team have?

To investigate the problem he decided to do some experiments in DoVL, which is a $$$p$$$-player versus $$$p$$$-player game. To start a game, each of the two teams need to pick $$$p$$$ distinct heroes of all $$$n$$$ heroes to form a lineup by ban pick phase, as described as follows.

• Ban Phase  Two teams take $$$b$$$ turns to ban a hero (to clarify, each team has $$$b$$$ turns), starting from the blue team. All heroes banned should be distinct. However, teams are allowed to decide not to ban any hero in any of their turns (known as an empty ban). The banned heroes can not be chosen in the pick phase by both teams.
• Pick Phase  Two teams take turns to pick heroes to form a lineup. The blue team first picks $$$1$$$ hero. Then starting from the red team, the two teams take turns to pick $$$2$$$ heroes, until only one hero is missing in one team's lineup, and that team finally picks their last hero. All heroes picked should be distinct and not banned.

To evaluate the lineup quality of picking, we follow three perspectives to calculate a score.

• Strength  Some heroes are naturally stronger than others in the current game. If one team picked hero $$$i$$$, they will earn $$$c_{ii}$$$ points.
• Combo  Some heroes will be stronger when working with one another. If two different heroes $$$i$$$ and $$$j$$$ are in the same team, the team will earn $$$c_{ij}$$$ points for such a combination. It's guaranteed that $$$c_{ij} = c_{ji}$$$, but you should not double count both $$$c_{ij}$$$ and $$$c_{ji}$$$.
• Counter  Some heroes make some specific opponents hard to perform well. If heroes $$$i$$$ and $$$j$$$ are in different teams, the team picking $$$i$$$ will earn $$$d_{ij} / 2$$$ points, while the team picking $$$j$$$ will earn $$$d_{ji} / 2$$$. It's guaranteed that $$$d_{ij} = -d_{ji}$$$.

Formally, suppose the lineup of the blue team is $$$(x_1, \ldots, x_p)$$$ and the one of the red team is $$$(y_1, \ldots, y_p)$$$. The total advantage (or disadvantage if negative) of the blue team can be evaluated by

$$$$$$ (\sum_{i=1}^p c_{x_i x_i} + \sum_{i=1}^p\sum_{j=i+1}^p c_{x_i x_j} + \sum_{i=1}^p \sum_{j=1}^p \frac 12 d_{x_i y_j}) - (\sum_{i=1}^p c_{y_i y_i} + \sum_{i=1}^p\sum_{j=i+1}^p c_{y_i y_j} + \sum_{i=1}^p \sum_{j=1}^p \frac 12 d_{y_i x_j}). $$$$$$

Given all the information above, can you help Oscar to calculate the advantage (or maybe disadvantage) the blue team will take when the two teams act optimally? It's not an easy task, so you may claim that you outperform the coaches of the world champions if you manage to solve this problem!

Once there was a rooted tree. The tree contained $$$n$$$ nodes, which were numbered $$$1, \dots, n$$$. The node numbered $$$1$$$ was the root of the tree. Besides, every node $$$i$$$ was assigned a number $$$a_i$$$. Your were surprised to find that there were several pairs of nodes $$$(i, j)$$$ satisfying $$$$$$a_i \oplus a_j = a_{\operatorname{lca}(i, j)},$$$$$$ where $$$\oplus$$$ denotes the bitwise XOR operation, and $$$\operatorname{lca}(i, j)$$$ is the lowest common ancestor of $$$i$$$ and $$$j$$$, or formally, the lowest (i.e. deepest) node that has both $$$i$$$ and $$$j$$$ as descendants.

Unfortunately, you cannot remember all such pairs, and only remember the sum of $$$i \oplus j$$$ for all different pairs of nodes $$$(i, j)$$$ satisfying the above property. Note that $$$(i, j)$$$ and $$$(j, i)$$$ are considered the same here. In other words, you will only be able to recall $$$$$$\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n [a_i \oplus a_j = a_{\operatorname{lca}(i, j)}] (i \oplus j).$$$$$$

You are assumed to calculate it now in order to memorize it better in the future.

Once there was a monkey, who was smart enough to press keys on a keyboard. However, he could not understand what he pressed. One day, a computer idiot came to the monkey for help. He needed to type a chapter of Complete Works of Shakespeare, denoted as a string $$$s$$$. When the monkey kept typing, he focused on the screen. As long as the chapter he wanted occurred on the screen as a substring, he would stop the monkey immediately and gain his result using ctrl-c and ctrl-v.

For simplicity, we assume that the keyboard only consisted of $$$26$$$ lowercase English characters, and the computer idiot didn't care about spaces, punctuation and capitalization, so $$$s$$$ only consisted of lowercase English characters. As the monkey actually didn't understand what he was typing, he pressed the keys randomly. The probability of the key $$$\beta$$$ pressed on each type was $$$p_{\beta} / \sum_{\gamma=a}^z p_{\gamma}$$$, and independent of what had already been typed.

The computer idiot waited for the Shakespeare's work he wanted on the screen till hungry and cold, so he asked you how long he had to wait in the words of mathematical expectation. The time was measured by the number of keys pressed by the monkey.

The question seemed easy for you, and after learning the result, the computer idiot realized that he might not be able to get Shakespeare's work while alive. Therefore, he decided to get a substring of $$$s$$$. In order to make a more reasonable decision, he asked you again the same problem on every substring of $$$s$$$.

Since there are too many substrings of $$$s$$$, you only need to output the sum of the expected time on each substring.

Throughout the problem, a substring means a continuous subsequence of another string.

Once there was a combination lock, which consisted of $$$m$$$ rings with digits from $$$0$$$ to $$$9$$$. It was broken so one could never open the lock no matter how he spun it. Alice and Bob wanted to play a game with it. They in turn spun one ring of the lock for one step in either direction, and tried to open the lock (although they knew the lock would never open). If the password on the lock had already been tried, the player would be considered lost. Additionally, they had discussed a set $$$S$$$ of $$$n$$$ passwords before the game started. The player would also lose if (s)he tried a password among $$$S$$$. Alice would move first.

A $$$5$$$-digit combination lock

Now you can only recall $$$m$$$, $$$S$$$ and the initial password on the lock, and you wonder who was the winner supposing Alice and Bob played optimally.

Once there was a courier named Kujou Kawaii, whose work was to collect packages from people around the city. The city consisted of $$$n$$$ communities, numbered from $$$1$$$ to $$$n$$$, together with $$$n - 1$$$ bidirectional roads connecting them. The express distribution center of this city was located at the community numbered $$$k$$$. Of course, any two communities were guaranteed to be connected by these roads. Kujou's electromobile was so small that she could only carry packages from $$$1$$$ community at the same time. She would always first deliver packages from the community numbered $$$1$$$, then those from the one numbered $$$2$$$, etc., and finally the packages from the one numbered $$$n$$$.

Let's calculate Kujou's tiredness index after a whole day of work! We only consider the trip from each community to the express distribution center. Unfortunately, Kujou had no sense of direction. On arriving at a community, she would uniformly randomly choose a road (including the one she came from) to follow, until she finally reached the community where the express distribution center was located. Suppose the trip from the community numbered $$$i$$$ to the express center passed $$$d_i$$$ roads. Kujou's tiredness was influenced by three factors.

1. Tiredness $$$a_i$$$ from beginning of the work. $$$a_i$$$ equals $$$i$$$.
2. Physical tiredness $$$b_i$$$ during the current delivery. $$$b_i$$$ equals $$$d_i$$$.
3. Emotional tiredness $$$c_i$$$. Kujor enjoyed traveling all over the city, so $$$c$$$ was initialized to $$$1$$$ for each delivery, and was multiplied by $$$x$$$ where $$$x$$$ is a rational number in $$$(0, 1]$$$ for each road Kujor passes. In other words, $$$c_i$$$ equals $$$x^{d_i}$$$.

It can be shown that $$$m_i$$$ can be expressed as an irreducible fraction $$$\frac{p_i}{q_i}$$$, where $$$p_i$$$ and $$$q_i$$$ are integers. It is then guaranteed in all test cases that $$$q_i \not\equiv 0 \pmod{10^9+7}$$$. In this case, $$$m_i$$$ modulo $$$10^9 + 7$$$ is well-defined, which is some integer $$$m'_i$$$ such that $$$m'_i q_i \equiv p_i \pmod{10^9 + 7}$$$. Furthermore, you only need to output $$$m'_1 \oplus \dots \oplus m'_n$$$ to prevent large output, where $$$\oplus$$$ denotes the bitwise XOR operation.

Once there was a painter, expert in drawing circles on a canvas. As a tasteful painter, he found that if he drew circles according to the following restrictions, the resulting canvas would look like an abstract painting.

1. The center of any circle must be a grid point on the $$$x$$$-axis.
2. The $$$x$$$-coordinate of any point on any circle must be within the range $$$[0, n]$$$.
3. The radius of any circle must be a positive integer not exceeding $$$5$$$.
4. Any two circles have at most $$$1$$$ intersection point.

Specially, an empty canvas was also considered an abstract painting, as it broke none of the above restrictions.

There had already been $$$k$$$ circles drawn on the canvas, not breaking the above restrictions. The painter could further draw one or more circles on the canvas to get an abstract painting, or he could draw nothing and claim that it was already an excellent abstract painting. He wondered how many different abstract paintings he could possibly get. As the number may be very large, you only need to output it modulo $$$10^9+7$$$.

Once there was a lovely ragdoll cat, named Little Zara, who liked trees and math. One day she met the doge Adam. Adam had just planted some trees each consisting of only one node. The nodes were numbered from $$$1$$$ to $$$n$$$, and the $$$i$$$-th node was assigned a value $$$a_i$$$. Adam liked pairing tree nodes, but he disliked some node pairs. A pair of nodes $$$(i, j)$$$ was considered bad if $$$i$$$ and $$$j$$$ were in the same tree and $$$\operatorname{gcd}(a_i,a_j)=a_i\oplus a_j$$$, where $$$\operatorname{gcd}(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$, and $$$\oplus$$$ denotes the bitwise XOR operation. Adam wondered how many bad pairs there were in his forest.

Zara was good at solving problems about trees and math, so she could answer Adam's question in a short time. However, Adam was so naughty a dog that he would repeatedly change the forest slightly and ask Zara his question again after the change.

The changes Adam might make are listed here:

1. Adam plants a new tree with only one node numbered $$$x$$$ and assigned a value $$$v$$$.
2. Adam uses magic to merge the tree containing the node $$$x$$$ and the one containing the node $$$y$$$. If $$$x$$$ and $$$y$$$ are in the same tree before the operation, the magic fails and has no effect.
3. Adam changes the value of node $$$x$$$ to $$$v$$$.

Now you are expected to help Zara answer all questions Adam asked, in order that they could sing and dance together happily.

Once there was a contest, where the last problem was about coordinate paper. You were given a piece of coordinate paper, where there were grids of $$$n$$$ rows and $$$10^{100}$$$ columns. The grids were initially white, and you might paint some of them black. In that problem, you were required to paint the paper in a special way. Suppose the number of black grids in the $$$i$$$-th row is $$$a_i$$$. Your painting was supposed to satisfy that

1. for any $$$i$$$, $$$a_i \geq 0$$$.
2. $$$\sum_{i=1}^n a_i = s$$$.
3. for any $$$i \in \{1, \dots, n - 1\}$$$, either $$$a_i - a_{i+1} = k$$$ or $$$a_{i+1} - a_i = 1$$$.

Can you still find an answer to that problem?