Bob is developing a new game called jumping Lario. In this game the main protagonist, Lario, has to jump on top of buildings until he reaches the end of the level. The level is composed of N buildings of possibly different heights. The building where Lario starts is chosen randomly at the beginning of the game.

Bob started to write the code for his game but then realized that he didn't know how to implement the jumps mechanics. The thing is, if Lario is currently on top of building X and the height of this building is h, then Lario should be able to reach building min(X + h, n) in one jump. Unless, of course, there's a taller building somewhere on the path from building X to building X + h, then in this case, Lario would face smash the taller building on the path and end up landing right before it.

For example, in the image bellow, if Lario had started on the first building (of height 5), with one jump he should be able to reach building six. But on the path from building one to building six, he would end up hitting building five that has height 6. When doing so, he would land on building four (the one with height 3).

Given the heights for all the N buildings, your task is to figure out for every possible start position of Lario, how far he would be able to go with just one jump.

After your death, you're sent to a mysterious room. There are two guardian cats and two doors, one goes to heaven of AC problems and another goes to hell NO. One cat likes all divisors of an integer a and the other cat likes all multiples of an integer b. You where asked to write all integers that satisfies both. If you answer correctly, you may go to heaven of AC problems, full of balloons, otherwise you're sent to hell NO.

Sancho is a weird kid, he really likes rectangles. You are in charge of babysitting him and you want to keep Sancho distracted. You decided to give him a gridded sheet of paper with many dots in it, so that Sancho can draw a lot of rectangles by connecting those dots.

You don't want him to get overwhelmed with too many rectangles, so you want to know what is the number of distinct rectangles that can be formed such that each of the rectangle's vertexes is a dot, there are no dots inside or on the edges of the rectangle besides the ones on its vertexes and all sides are parallel to the axis of the grid.

Samuelo is a very good friend of Roppa. Whenever they feel bored, they like to exchange secret messages.

To do that, they craft some text in such a way so that the hidden message is a subsequence of it. To make things harder, they never use whitespaces.

An example of message exchanged in the past is (hidden message is red and underlined):

It can be very hard to uncover a message hidden like that, but it's usually not a problem for them since their minds are pretty much in sync.

Samuelo just wrote one of those messages. Roppa decided to take a step further this time and test their friendship by trying to guess the hidden message before even receiving it.

Given the message that Samuelo wrote and Roppa's guess, help Roppa on figuring out if his guess is in fact hidden in Samuelo's message.

Chi is a little kid that goes to a middle school in London, Ontario. He is in a band, and they are planning on performing this weekend. There are $$$N$$$ members in this band, and each one is categorized by the id of the instrument that they play, represented by a number $$$V$$$, and their ability level represented by a number $$$P$$$.

The enjoyment of a performance depends on the order in which people play, and their ability levels. The playing order goes as follows: the order of people presenting has to be in the order of their instrument's id, from smallest to largest, and in case of ties any order of the people with the same instrument is valid. If two people in a row are playing the same instrument, the enjoyment level doesn't change. If two people in a row have different instruments, the enjoyment increases by the absolute diference of their ability levels, because people like to see very different kinds of performances even if the ability level decreases.

Chi wants to have the best performance ever, and he asked your help with this task. He wants to know what is the highest enjoyment of the performance, given an optimal ordering.

You have a box with N cards numbered 1...N and you can also create new cards.

You are going to draw cards from the box, every time you draw a card of a number that has already been drawn you put that card back into the box. If you draw a card of a number that has not been drawn before, you lay it on the desk and you create another card to put back into the box. The number of the new card is chosen randomly with the same probability from the interval [1, N].

In this problem you have to answer what is the expected number of cards on the desk when you draw a card numbered 1 for the first time.

Tomaz and Danftito are playing a game with 3 stacks of rocks, each with a, b and c rocks respectively. Each turn, a player must take from 1 to m rocks from a stack, but they can't empty a stack if there are rocks in any stack to the left. The player that removes the last rock wins. If Tomaz goes first and they take turns playing, determine who will win the game if both players play optimally.

A sequence of numbers A is said to be logarithm concave if, and only if, for every 2 ≤ i ≤ n - 1, a_i - 1 * a_i + 1 ≤ a_i².

For example the sequence A = (1, 2, 3) is logarithm concave. The sequence A = (2, 2, 3) is not logarithm concave.

In this problem, you will have to answer what is the number of log concave sequences which contain only the numbers 0, 1 or 2, with N elements.

As this number could be very large, print the answer mod 10⁹ + 7.

Laersh is a Pokemino trainer and he just captured his first pokemino. Throughout his journey he will capture more Pokeminos. Each Pokemino has an attack and a defense level. A Pokemino is better than another one if it has greater attack and greater defense level. Besides capturing Pokeminos, Laersh can breed any two Pokeminos that he owns and generate a new Pokemino. This new Pokemino's attack and defense will be a linear combination of its parents attributes:

Attack_child = Attack_parent1 * c + Attack_parent2 * (1 - c)

Defense_child = Defense_parent1 * c + Defense_parent2 * (1 - c)

The number c is the same for attack and defense, and can be any number 0 ≤ c ≤ 1.

An useless Pokemino is a Pokemino such that Laersh owns a better Pokemino, or he can breed a better Pokemino. For each new Pokemino that Laersh captures, help him figuring out the number of useless Pokeminos that he owns.

Sanchola is getting an array of integers as gift. He's weird, so he doesn't like having distinct integers in the same array and he only likes prime numbers. That's why he believes that he might need to fix the array after receiving it by turning all elements into the same prime number.

Sanchola is also very lazy and wants to do that using the minimum number of operations. In one operation Sanchola can either increase or decrease a single element of the array by one.

Given the array that he received as a gift, help Sanchola figuring out the minimum number of operations required to fix the array.

Nicoleta received a box of candies from his sister. It has a rectangular shape with dimensions $$$1$$$ x $$$N$$$ and contains $$$N$$$ candies, and each one has a value $$$C_i$$$ of deliciousness.

Sanchola lives with Nicoleta in Revuocnav and he loves to make Nicoleta upset. Sanchola found out about the gift and decided to take a consecutive subsequence of candies from the box when Nicoleta is not looking. The total deliciousness taken by Sanchola should be at least L so that he can enjoy the candies, but not greater than R, to not raise suspicion.

Sanchola needs your help to calculate the number of distinct consecutive subsequences that he can take from Nicoleta.

Two consecutive subsequences $$$C_{l_1} \cdots C_{r_1}$$$ and $$$C_{l_2} \cdots C_{r_2}$$$ are considered equal if and only if they have the same number of candies $$$x$$$ and $$$\forall{k}$$$ $$$C_{l_1 + k} = C_{l_2 + k}, 0 \leq k \lt x$$$.