A programming competition will be held in Nlogonia to determine who is the best Nlogonian programmer of all time.

The competition will have $$$N$$$ contestants and there are no ties, in other words, every contestant will be ranked in a position from $$$1$$$ to $$$N$$$ and all ranks are distinct. Lower ranks represent better results.

The event organizers decided that each contestant will receive a prize of at most $$$R$$$ rating points, and, to be fair to the competitors that performed better, a contestant will never receive fewer rating points than any other contestant with a worse ranking.

Some competitors, though, are more greedy and want to receive more rating points to be happy. A contestant with rank $$$i$$$ needs to receive a prize of at least $$$p_i$$$ rating points to be happy.

Ina, a very curious organizer, is wondering in how many ways it is possible to distribute the prizes to the contestants in order to satisfy the organization's conditions and make all contestants happy. Also, since this number can be very large, you should calculate it modulo $$$10^9+7$$$.

Two ways are different if at least one contestant receives a different prize amount.

You are given a string $$$A$$$ of length $$$N$$$ and a set $$$S$$$, containing $$$M$$$ strings.

A cyclic permutation $$$B_i$$$ of $$$A$$$, in which $$$i$$$ is between $$$1$$$ and $$$N$$$, is the string

and its score is defined as the maximum length of a substring of $$$B_i$$$ that is also a substring of some string in $$$S$$$.

A substring is defined as a contiguous sequence of letters. For example, ab and dc are substrings of abfdc, but ad and fc aren't substrings of abfdc.

Your task is to calculate the minimum score over all cyclic permutations of string $$$A$$$.

Malba is a very smart kid who loves to perform calculations. He has won several competitions, including the prestigious Tahan competition, in which he got the first prize, representing his country, Logonia.

He created a puzzle, in which he considers a number $$$N$$$, written in a certain base $$$B$$$, and represented by $$$L$$$ digits. The objective of the game is to reduce at most one of the digits so that the new number, $$$M$$$, be a multiple of the number $$$B+1$$$. But there is a catch: among the possible solutions you must choose one that renders $$$M$$$ the smallest possible value.

For example, suppose that $$$B=10$$$ and $$$N=23456$$$. There are two ways in which $$$M$$$ may be obtained: either we reduce the digit 4 to 0 or we reduce the digit 6 to 2. Thus, 4 must be changed to 0, hence $$$M=23056$$$. Sometimes there is no solution, as is the case if $$$B=10$$$ and $$$N=102$$$. In this case, if we change the digit 1 to 9 we get a multiple of 11, but we are not allowed to increase the value of a digit!

Observe that it may be necessary to reduce the first digit to 0. For example, this is the case if $$$B=10$$$ and $$$N=322$$$.

Can you tell which digit should be reduced and what is its new value?

The kingdom of Nlogonia has historically been a very wealthy and quiet place. However, the current circumstances could bring this era of peace and prosperity to an end: The king is a father of two twins, so both of them are heirs to the throne.

The twins don't get along well and are jealous and overly competitive towards each other. Due to this, having both of them rule over the kingdom cooperatively is not a viable option. The kingdom will have to be divided into two independent principalities so that each of them can be given to each prince. Also, the division needs to be totally fair to avoid conflict between the envious brothers.

The kingdom consists of $$$N$$$ cities and $$$M$$$ roads connecting pairs of cities. The Nlogonians are peculiarly proud of their roads. Each road has an associated positive value which represents its beauty.

The kingdom will be divided in this manner: First, the cities will be partitioned in two sets such that every city is in one and only one set. Then, each principality will consist of the cities in one set and the roads connecting cities of this same set. Roads that connect cities of different principalities will be destroyed, as the princes are not interested in trading with each other, and keeping the roads would only make war more likely.

The beauty of a principality is defined as the maximum beauty of the roads within the principality, or $$$0$$$ (zero) if the principality has no roads at all. For obvious reasons, the king would like the beauty of both principalities to be the same.

Help the king determine all the possible values of the beauty of the resulting principalities, given that the division is made in such a way that the principalities are equally beautiful.

You have just invented a new type of escalator: the double escalator. Regular escalators take people from one endpoint to another but not in the other direction, while the double escalator can take people from any one of its endpoints to the other one.

It takes 10 seconds for the double escalator to take a person from any of its endpoints to the other one. That is, if a person enters the double escalator from one of the endpoints at moment $$$T$$$, then they will leave at the other endpoint at moment $$$T + 10$$$ – this person won't be using the double escalator anymore at moment $$$T + 10$$$.

Any time that no one is using the double escalator, it will stop immediately. Thus, it is initially stopped.

When the double escalator is stopped and a person enters it from one of its endpoints, it will turn on automatically and move in the direction that this person wants to go.

If a person arrives at the double escalator and it is already moving in the direction that they want to go, they will enter it immediately. Otherwise, if it's moving in the opposite direction that they want to go, they will wait until it stops, and only then will they enter it. The escalator is so large that it can accommodate many people entering it at the same time.

The double escalator has a very weird effect, probably related to some quantum physics effect (or just chance): no person will ever arrive on the double escalator at the exact moment the escalator stops.

Now that you know how the double escalator works, you will be given the task of simulating it. Given the information about $$$N$$$ people, including their time of arrival at the escalator and which direction they want to go, you have to figure out the last moment that the escalator stops.

Michael and his brother Lincoln are unfairly imprisoned in the same prison, but Michael has a plan to rescue his brother. The prison can be seen as a set of convex polygons in the plane, in which the edges of the polygons are walls. The walls of distinct polygons do not intersect, but polygons may be nested, that is, inside one another. Michael and Lincoln can be seen as two points in the plane. The rescue path will be for Michael to reach his brother and then both of them need to escape the prison.

Walking for them is no problem, but climbing walls is dangerous and difficult, so Michael will try to minimize the total number of walls climbed by him. So Michael first needs to climb some walls to reach his brother if they are not within the same area and then climb some more walls to leave the prison. Leaving the prison means not being within any walls, which can be seen as reaching a point very far away, let's say $$$(10^{20},10^{20})$$$. Brad is in charge of the placements of the prisoners and is aware of the plan, so he will place both prisoners in two different points in the plane not contained by any segments and such that the minimum amount of walls that need to be climbed by Michael is maximum. What is the minimum amount of walls to be climbed if Brad places the brothers optimally?

Illustration for valid placement in Example 1. Point M represents Michael and point L represents Lincoln

Illustration for valid placement in Example 2

Juan decided to start working out and is willing to prepare a workout session.

He knows that some days he might not want to do all exercises from his workout session. He decided on some rules to avoid skipping the whole session and not exercising at all, while still allowing him to optionally skip some exercises.

The rules are:

• There will be only two types of exercises: $$$A$$$ and $$$B$$$.
• After finishing an exercise of type $$$B$$$ he moves to the next exercise, if there is one. Otherwise, the workout session ends.
• After finishing an exercise of type $$$A$$$ there are two possibilities: he can move to the next exercise, or he can skip the next exercise and move to the one after that.
• The last exercise in a workout session must always be of type $$$B$$$.

Therefore, there might be different ways in which the workout session can be completed. For example, if the types of exercises in a workout session are $$$\texttt{BAAB}$$$, there are 3 ways in which the session can be completed: by doing all exercises, by skipping the 3rd one or by skipping the last one.

Juan wants to prepare his workout session in such a way that there are exactly $$$N$$$ different ways in which the workout session can be completed. Can you help him?

A friend of yours invented a game and wants to know if you can solve it or if it's impossible.

He assembled a sequence of $$$N$$$ blocks. Each block has a number engraved on it and some color. All numbers are distinct and between $$$1$$$ and $$$N$$$, and different blocks can be of the same color.

The game works as follows: you can play as many turns as you want. In one turn, you choose two different blocks that share the same color and swap them.

You have to tell whether it is possible to get the entire sequence to be sorted into ascending order by numbers engraved on the blocks.

The government in Nlogonia is bothered by the lack of efficiency of their railroad system. Each pair of cities is connected by a single railroad, but due to budgeting issues, some of these are inactive.

An ideal railroad configuration is one such that for every pair of cities there is exactly one path that connects those cities using only active railroads.

The Nlogonian governor hired you to transform his set of railroads in an ideal configuration. You, unfortunately, don't speak Nlogonian nor can change the activeness of the railroads: only the leader of each city, all of which only speak Nlogonian, can activate or deactivate them.

Nlogonian has some really specific phrases, so you hope you can count on that. You have a friend that speaks Nlogonian, and to help you (and also challenge you a little bit), he taught you a phrase that you can try using: "lupDujHomwIj luteb gharghmey". He said that if you say that to a city's leader, then the leader will activate all railroads that are connected to their city and that were previously inactive, and deactivate all railroads that are connected to their city and that were previously active. In other words, the "activation" status of all railroads that connect to that leader's city will be flipped.

Result of "lupDujHomwIj luteb gharghmey" cities 1 and 2

Knowing this phrase, you can call some leaders and make them "lupDujHomwIj luteb gharghmey" their cities' railroads.

Your friends doubt that you can make the railroad system ideal by only using this phrase. You really want to prove them wrong. You said you will not only find a solution but tell in how many different ways you can achieve that. More precisely, we say a set of leaders is good if by contacting them and only them once, an ideal configuration is achieved. You want to tell your friend how many distinct good sets of leaders there are.

Two sets of leaders are distinct if there is at least one leader that is in one of the sets but not the other.

Since this number may be large, you must output it modulo $$$10^9+7$$$.

Football hasn't always been the most popular sport in the Americas. Historians have found records of an ancient sport that was played in many civilizations across the continent. Because of the lack of spoken tradition about it, the original name is unknown, but in modern times it has been very creatively named "bootfall".

We don't know a lot about bootfall, not even the basic rules. However, archeologists have found a lot of notes made by bootfall coaches when trying to assemble their teams, which give us some information about how teams were formed. These notes are filled with numbers and calculations. Bootfall coaches meticulously tried to optimize their team by assigning players to the best positions possible. To facilitate this task, they developed a metric for determining the performance of each arrangement.

There are $$$M$$$ positions in a bootfall field, which are distributed in a line. A bootfall team consists of $$$N$$$ players, each of which is assigned to some position (all players should be assigned to exactly one position, each position can be occupied by one or more players or can be left unoccupied).

Naturally, players are not equal to each other: Each player can have a different performance when playing in different positions in the field. Concretely, for each player $$$i$$$ and each position $$$j$$$, there is a positive value $$$P_{i,j}$$$ which represents the performance of player $$$i$$$ when playing in position $$$j$$$.

To complicate things further, coaches also consider the aspect of player interaction. Some pairs of players are "best friends". When best friends are far from each other in the field, that harms team performance. There's a positive value $$$C$$$ which represents the performance penalty that is paid when moving best friends away from each other.

Once players are assigned to positions, the value of the team performance is calculated as follows: First, we add up the performances of the players when playing in their assigned position. Then, for each pair of players who are best friends, we subtract $$$C$$$ times the distance between the two players, where the distance between two players is defined as the difference (in absolute value) between the positions to which the players were assigned.

We want to know how good bootfall coaches were at forming teams. In order to do that, we would like to know what is the maximum possible value of team performance achievable by arranging the players in the optimal positions, given the performances of the players in each position and the pairs of players who are best friends.

The pandemic is getting better and you can finally do the thing you've been dreaming of for the past few years: eat at your favorite restaurant! The restaurant happens to be in Kathmandu, but that's fine, you can always take a plane.

The problem is that planes almost always leave you restless. You consider yourself properly rested if you can sleep for $$$T$$$ uninterrupted minutes, which means you are never awake from a certain moment $$$t$$$ to $$$t+T$$$. Also, you're a very easy sleeper: you can fall asleep at the start of any minute and wake up at the end of any minute.

Of course, if you sleep too much you will miss all the airplane meals! That is unacceptable, as no opportunity for free food should go to waste.

Luckily, the airplane company sent you the whole flight schedule: the duration of the flight, $$$D$$$ minutes, the number of meals that are going to be served, $$$M$$$, and the exact time they will serve the meals, $$$y_i$$$. You need to be awake at the time the meal is being served to be able to eat it, otherwise, the steward will not serve you. Since you're always hungry, you will devour the meal instantly.

Now you are wondering, for the optimal plane traveling experience, can you get properly rested and still eat all meals during the flight?

Michael is the manager of a barely known office and inside his room there is a locker with the money to pay the employees. Unfortunately, Michael forgot the password of the locker and it is now Dwight's responsibility to help his boss.

The password is a sequence of $$$N$$$ digits, containing only zeroes and ones, and Michael remembers the value at some positions of the sequence, but not the whole password. Michael also remembers $$$M$$$ intervals of the password that are palindromes – his mind memorizes palindromes, for some reason.

An interval is a palindrome if, and only if, the first and last digits of the interval are equal, the second and second to last digits are equal, and so on.

Now Dwight wants to know how hard it will be to recover the whole password. You can help Dwight by calculating the number of possible passwords that follow what Michael remembers.

Since the answer may be very large, output it modulo $$$10^{9}+7$$$.

Monarchy succession can be a tricky topic as it might take into account multiple factors such as descent, sex, legitimacy, and religion. Usually, the Crown is inherited by a sovereign's child or by a childless sovereign's nearest collateral line. Not really straightforward, right? And that's one of the reasons why, all over the world, monarchy is on the edge.

Nlogonia is still ruled by a monarchy though, luckily with simple succession rules. In general, there are only two aspects to take into account: "children comes before siblings" and "older comes before younger".

The reign servants maintain a beautiful and enormous tapestry where the bloodline of Constant, Nlogonia's first ruler, is drawn in the shape of a tree. Whenever a new family member is born a new branch from the parent to the child is drawn in the tapestry. This is such an important event that legend says that when Constant's descendants have a child they will never die before watching their child's name added to the tapestry. When someone dies, a cross is drawn close to that person's name. Whenever the current monarch dies, the tapestry is used by the servants to determine who the next ruler should be. In order to determine who that person is, the servants start from Constant and traverse the tree according to the rules described earlier, "children comes before siblings" and "older comes before younger". They descend the tree starting from Constant, followed by Constant's first child, followed by that child's first child, and so on, until reaching the first person alive or a family member that has no children left to follow, in which case they then go back to that person's parent and move into that parent's next child, repeating the process until the new monarch is determined.

After thousands of years in power Constant's bloodline is huge. To maintain the tapestry and, when the time comes, to determine who the next monarch should be are lengthy processes and Nlogonian servants decided it's time to modernize. They want to create a program to be used to maintain Constant's bloodline, which can also point who the next monarch should be after a ruler's tragic death. Given the importance of this task, the monarchy servants want to test the program by checking that it produces the correct output for all events that happened so far. There is one issue though, none of them is really good with programming and that's why they came after you for help.

More technically, each person in Constant's bloodline will be represented by a unique positive integer identifier. Whenever a new child is born, they take the next lowest unique identifier. Constant's identifier is equal to 1, and initially he's the only person alive. You will be given many events to process, in chronological order. Whenever someone dies, you should help the monarchy servants to figure out who the current monarch is. It's guaranteed that there will always be someone alive to rule.

Vini is a very dedicated car painter. Ever since he learned how to paint cars, his dream was to participate in the International Competition for Painting Cars (ICPC for short).

Every year Vini's region has a local competition to rank all teams of competitive car painters from this region. Painters in teams that were ranked in the top $$$x$$$ spots will then go on to compete in the ICPC. It is a very thrilling competition with lots of new competitors every year, until the noxious fumes from the car paint eventually leads them to permanently retire.

Because of the variance in the national car painting budget and ICPC constraints, this number $$$x$$$ may vary between years, which may cause a lot of displeasure in some competitors.

On Vini's last year as a contestant, his team was a single position away from qualifying to the ICPC. How unlucky! To make his "bad luck" feeling worse, in the following year the team who got the same position did qualify! Despite this feeling, after talking to other former contestants, he noticed that many have had the same feeling of being unlucky in one way or another.

Former contestants usually follow the results of the regional competition for a few years after retiring. Hence, a contestant would not feel unlucky for changes in $$$x$$$ that occur many years after they retire. More precisely, each former contestant had their last participation in the year $$$a_i$$$, being placed in the position $$$p_i$$$ and, after retiring, followed results for the next $$$f_i$$$ years.

A contestant that didn't qualify to the ICPC in their last participation has felt unlucky on every year that they followed the results in which they would qualify to the ICPC if they had competed in that year. In other words, for every year up to $$$f_i$$$ years after the contestant retired, if they didn't qualify in their last participation, they felt unlucky if the number of teams that qualify for the ICPC in this year was at least $$$p_i$$$.

Given the number of slots per year and the information about the former contestants, we want to know how many years each former contestant felt unlucky.