William is employed at a local factory in his dream job: middle management.

Taking the assembly line to heart, the factory contains $$$N$$$ workers, who reside on a line. Each individual $$$i$$$ has a productivity $$$p_i$$$ and works $$$h_i$$$ hours. Their individual output is given by the product of these two values.

As he is the most senior middle manager, William gets the first pick of his team. William is expected to manage a team of $$$K$$$ people and his bonus is the total output of his managed workers, in dollars. Of course, the team must be contiguous to ensure sufficient team bonding.

Please help William determine the optimal team and more importantly, tell him what he truly cares about, his bonus.

William has baked a cornmeal pudding pone! They have invited all their friends over to share the dessert. However, they need your help to divide it evenly among all friends.

William wants all of their friends to have an equal number of slices. However, they don't know how many friends will actually show up. Friends show up in groups (where the total number of groups is $$$N$$$), and William cuts the pone in the following manner:

1. The $$$i$$$th group of friends shows up, which consists of $$$a_i$$$ people.
2. If the pone is currently cut into $$$s$$$ slices, William cuts the pone into $$$k \cdot s$$$ equal slices for some integer $$$k$$$, such that each person present ($$$a_1 + ... + a_i$$$ people total) can eat an equal number of slices. (But they don't eat it yet!)

The pone starts off unsliced. William wants to know – after everyone (all $$$N$$$ friend groups) show up, what's the minimum number of slices the cake will be cut into that satisfies the given technique?

See the notes for a more detailed example.

William is playing a game with a robot. In this game, there is an array of $$$n$$$ integers in a line, numbered $$$1, \ldots n$$$. $$$n$$$ is even.

William and the robot take turns selecting integers from the array, starting with William. William can take an integer from anywhere in the array as long as it has not already been taken by any player. The robot always takes the leftmost, untaken integer (i.e. the one with the lowest index). The game ends once all integers have been taken. William's score is the sum of his chosen integers.

Help William get the maximum score possible.

William likes to play card games. In this particular game, William is dealt a row of $$$N$$$ playing cards. Each of the cards has a positive integer point value, where the $$$i$$$-th card in the row has a point value of $$$p_i$$$.

The object of the card game is to minimize the maximum point value among all of the cards that William has. To do so, William is allowed to perform operations. For any $$$1 \leq i \lt N$$$, William may halve $$$p_i$$$ and double $$$p_{i-1}$$$ so long as $$$p_i$$$ is an even number. William may perform as many operations as he desires.

If William performs operations optimally, can you figure out the minimum maximum point value that he can achieve?

William is overseeing a system of spaceports in the galaxy of Glarble. Because space trips are expensive, spaceports generally try to have as few unnecessary flights as possible. In particular, the (two-way) flights can be represented by a tree, such that each planet in Glarble can be reached by each other planet in Glarble through some sequence of flights, but this sequence is unique (there is only one path from one planet to another).

Because different planets have different resources, each planet has an associated cost of visiting the planet. The cost of a trip from planet $$$u$$$ to planet $$$v$$$ ($$$u \neq v$$$), then, is the sum of the costs of all planets visited on the distinct path from $$$u$$$ to $$$v$$$. The total cost of the spaceport system is the sum of the costs of all distinct trips, where two trips are the same if they have the same starting planet and the same ending planet. Trips and flights begin and end on different planets.

William has the technological ability to upgrade spaceports; when he upgrades a spaceport, its cost decreases by one, unless the cost is already 0 in which case nothing happens. He can upgrade spaceports $$$K$$$ times (not necessarily distinct spaceports). He then wants to know: if he does this optimally, what's the minimum total cost of his new spaceport system?

William and will.i.am are the host and judge, respectively, of a rap battle tournament! The $$$N$$$ contestants will perform on one of two different tracks selected by will.i.am. For each contestant, we know their "rap skill level" on each track. When two players battle on a specific track, the player with higher rap skill level on that track always wins. No two players have the same rap skill level on the same track.

The tournament consists of $$$N-1$$$ battles, and the tournament will proceed as follows:

1. Randomly select two players still in the tournament.
2. Choose a track out of the two available ones for the players to battle on.
3. The player that wins the individual fight will continue on in the tournament, and the loser will be eliminated.
4. Go back to step 1 and repeat until a single player remains.

William would like to quantitatively measure how "interesting" the tournament structure is relative to other ideas he has, which is directly proportional to the number of possible winners of the tournament. Can you help William find the number of contestants that have a shot at winning it all?

Today is William's 26th birthday! As such, his friends have gifted him an array of length $$$N$$$. Since he is turning 26, the array will consist of only the 26 letters of the English alphabet ($$$\{\text{a}, \text{b}, \dots, \text{z}\}$$$). However, William's friends are super picky – they want the array to be perfect before they present it to William. Each of William's $$$Q$$$ friends have a chance to either make a change to the array by changing the letter at a certain index to a different English letter, or to inspect a contiguous subarray of the array and check how many palindromes the letters within the subarray can create. A palindrome is a string which is read the same forwards and backwards.

For example, if the array initially looks like $$$\{\text{q}, \text{q}, \text{r}, \text{a}, \text{r}\}$$$, and William has 2 friends, then William's first friend may choose to change the letter $$$\text{q}$$$ at index 1 to the letter $$$\text{a}$$$, resulting in the array becoming $$$\{\text{q}, \text{a}, \text{r}, \text{a}, \text{r}\}$$$, and his second friend might inspect the contiguous subarray starting at index 1 and ending at index 4 ($$$\{\text{a}, \text{r}, \text{a}, \text{r}\}$$$). The second friend will then realize that there exist 2 possible palindromes using exactly these letters ($$$\text{arra, raar}$$$). Note: when executing an inspection, the friend must use all of the letters in the range to construct palindromes.

Since William has many friends and each friend would like to perform one of these two types of queries (and because the array they are working with is very large), they need help doing all of the necessary computations. Please help them out!

For celebrating Diwali, William created rangoli in the shape of a regular polygon with $$$n$$$ vertices, where $$$n$$$ is even. $$$m$$$ of the vertices of the polygon in a row are all white, and the remaining $$$n - m$$$ nodes are black. Each of the edges of the polygon are connected with purple lines.

To fill in the polygon, William first creates a triangulation of the polygon, again using purple edges and only drawing non-intersecting diagonals. Now, William fills in the each of the triangles. If all three vertices of the triangle are the same color, William is unhappy, so the triangulation would be invalid. Otherwise, if there are 2 black vertices and 1 white vertex, the triangle is colored black. Similarly, if there are 2 white vertices and 1 black vertex, the triangle is colored white. In the end, William wants there to be $$$k$$$ white triangles and $$$n - k - 2$$$ black triangles for the triangulation to be valid.

William is having trouble deciding which triangulation he wants to use. How many possible valid triangulations are there? Because the answer may be large, compute it modulo $$$10^9 + 7$$$.

William loves making necklaces. He has an infinite number of each letter 'a'...'z', and wants to arrange them in a circle to make a necklace of length $$$n$$$, where $$$n$$$ is prime.

However, William only wants to make good necklaces. A necklace is considered good if it does not contain the string $$$s$$$, even after rotation.

Help William count the number of distinct good necklaces he can make. Two necklaces are the same if one can be rotated to be equal to the other. "abab" and "baba" are the same, but "abab" and "aabb" are distinct.