The Olympic Games in Paris are almost here, and you are thrilled! You and four of your friends managed to get five of the rare tickets for sports climbing even though all tickets were sold out in less than two hours! While waiting for the games to start, you decide to do something fun to keep your mind off the wait: play your favourite card game.

The card deck contains four standard suits of different colours: silver (S), white (W), emerald (E), and red (R), as well as one trump suit coloured cyan (C). That is, the Cyan cards outrank all other cards. There are $$$N$$$ cards of each suit, numbered from 1 to $$$N$$$. This means that, in total, the deck comprises $$$5N$$$ cards. At the beginning of the game, the deck is randomly distributed between the five players, such that each player gets $$$N$$$ cards.

Before you start playing, you want to organise your cards such that all cards of the same suit are next to each other in increasing order, and the trump cards appear at the end (also in increasing order). When you receive your cards, they appear in your hand as a sequence. To organise them, you perform a sequence of actions, where in each action you take one card out of your hand and put it back in your hand at another position (between two cards, before the first card, or after the last card).

You cannot help but wonder: what is the minimum number of actions you need to take in order to organise your hand?

Alice is attending a sport event with many national teams and one thing is important to her: supporting every country.

There are $$$N$$$ countries represented and she has two ways to support a country: either have the flag drawn on her or have a pin with the name of the country. Alice has a list containing, for each country, the colours needed to make its flag. A total of $$$M$$$ colours that may appear across all flags and, in Alice's list, each colour is conveniently represented as an integer between 1 and $$$M$$$.

Each crayon and pin cost 1, but her budget is tight... Can you help her find the minimum she can spend to support everyone?

Two Olympics spectators are waiting in a queue. They each hold a copy of the metro map of Paris, and they devised a little game to kill time. First, player A thinks of a metro line (chosen uniformly at random among all metro lines) that player B will need to guess. In order to guess, player B repeatedly asks whether the line stops at a metro station of her choice, and player A answers truthfully. After enough questions, player B will typically know with certainty which metro line player A had in mind. Of course, player B wants to minimise the number of questions she needs to ask.

You are given the map of the $$$M$$$ metro lines (numbered from 1 to $$$M$$$), featuring a total of $$$N$$$ metro stations (numbered from 0 to $$$N-1$$$) and indicating, for each line, those stations at which the line stops. Please compute the expected number of questions that player B needs to ask to find the answer, in the optimal strategy.

In other words, given a strategy $$$S$$$, note $$$Q_{S,j}$$$ the number of questions asked by the strategy if the metro line in the solution is line $$$j$$$. Then, note $$$$$$ E_S = \mathbb{E} \left[ Q_S \right] = \frac{1}{M} \sum_{j = 1}^M Q_{S, j} $$$$$$ the expected value of $$$Q_{S,j}$$$ assuming that $$$j$$$ is uniformly chosen from the set of all metro lines. Your task is to compute $$$\min_S E_S$$$.

If it is not always possible for player B to know which line player A had in mind with certainty, output not possible.

You are in charge of a team of sorted gymnastics. This new discipline involves teams of $$$N$$$ members. Each team member dresses with a different colour (a number from 1 to $$$N$$$) and holds a coloured flag. Flags have unique colours, also numbered from 1 to $$$N$$$. A performance consists of exactly $$$K$$$ steps. At each step, two members exchange their flags. You are free to choose the initial configuration of the flags. The only constraint is that, at the end of the performance, each participant must hold the flag corresponding to the colour of his outfit.

Being the team captain, you would like the performance to be as unpredictable as possible. You consider $$$T$$$ possible initial configurations of flags among the team members, and wonder: in how many ways can the team perform the task for each of these initial configurations ?

For each of the given $$$T$$$ initial configurations, compute the number of possible ways to do the performance. As the answers may be very large, return them modulo the prime number $$$1~000~000~007$$$.

Paris is so crowded with tourists during the Olympic games! You want to escape the city and go on a hike on a linear trail path, going from left to right. Every kilometre on that trail, including at start and end, is a milestone, on which is written the stone's altitude. The slope between two consecutive stones is constant, and no two stones have the same altitude.

Planning to come back with your friends, you try to identify the point of the hike at which you had the nicest view. The beauty of a point of view is defined as the distance (measured in kilometres) between your position and the leftmost position that you can see on your hike and that is at the same altitude as you are. If such a previous position fails to exist, it means that you can see the city and its smog, and the beauty of that view is zero.

You have listed the altitudes of the milestones. What is the maximal beauty on your hike?

 

Programming competitions are fun and exciting. Programming should be an Olympic sport! At least, this is what we believe. However, when we suggested this to some of our friends, they did not seem to share our excitement. So, we decided to suggest a combined sport that will be more interesting to watch. Programming-trampoline-athlon! (we are still working on the name.)

The idea is as follows. This is a team sport, where each team comprises of 3 members. The team has at its disposal 1 hour, 1 computer, and 1 trampoline. At all times, there must be at most one team member using the computer and at least one team member jumping the trampoline. At the beginning of the competition, the team is given 6 programming problems, and 6 trampoline elements (exercises). The team decides how to partition the trampoline elements between its members, such that each team member has to perform 2 of the given elements on the trampoline. The programming tasks are solved cooperatively by the team members, but no one member can spend more than 25 minutes on the computer in total. The scoring is comprised of two parts, which are added together:

• The programming score ranges between 0 and 60. The team receives 10 points for every correctly solved problem.
• The trampoline score ranges between 0 and 40. Each of the 6 trampoline elements receives a score from the judges that ranges between 0 and 10. The final trampoline execution score is determined by dropping the highest and lowest of the 6 scores, and then adding up the remaining 4 scores.

Before we pitch this new sport to the International Olympic Committee, we want everything to be ready in order to show them just how serious we are. Thus, each team should receive a medal when no more than two other teams obtained a strictly higher score. However, in order to cope with a recent shortage of medals, the jury was instructed to make sure that there would be no more than 1 000 teams deserving a medal. We ask you to write a program that determines the medallists, given the performance of the different teams.

France is a country of gastronomy. For a dish, both the taste and plating are important. Nevertheless, when different people evaluate a dish, some focus more on taste and some focus more on plating. At the Olympic Village dining hall, there are $$$N$$$ dishes, numbered from 1 to $$$N$$$; each dish has a score on its taste and a score on its plating. There are also $$$M$$$ persons, numbered from 1 to $$$M$$$; each person has a weight on taste and a weight on plating. One person's final score of a dish is the weighted average of the dish's scores on taste and plating.

The chefs at the Olympics want to provide everyone with their favourite dish on the evening of the closing ceremony. Your task is to calculate everyone's favourite dish. If multiple dishes tie for the highest score as a person's favourite, choose the one with the smallest number.

For the first time, breakdance will be featured in the Olympics. And you get to participate! Well, you get to participate to the jury... More precisely, you get to build the table in front of which the jury will be seated: still, that is an impressive feat, congratulations!

Actually, the top of the table is already built: it is plane, has constant width and constant density, and its shape consists in the interior of an $$$N$$$-sided non-crossing polygon $$$P_1 P_2 \dots P_N$$$ in which no three vertices are collinear (i.e., no line goes through three vertices or more). You have three table legs of same length and negligible width. Your task is to place them at distinct corners of the table so that the table remains stable when standing on these legs. In other words, you must choose three vertices $$$P_i$$$, $$$P_j$$$ and $$$P_k$$$ of the polygon such that the centre of gravity of the polygon lies in the interior of the triangle $$$P_i P_j P_k$$$ (and not on its boundary).

In how many different ways can you do this? If two ways of placing legs differ only by a permutation of the legs, they are not counted as different ways.

Alice and Bob are discussing penalty shoot-outs and their randomness: "We might as well be throwing dice to determine the winner!", Alice said. And so they started simulating penalty shoot-outs by each throwing dice, summing the points indicated on their dice, and comparing these sums. The player with the largest sum wins; in case both sums are equal, there is a tie.

But even in such situations, some player might have an edge over their opponent, depending on which dice they throw. Thus, just by looking at the dice they are about to throw, Alice and Bob want to determine who has the better edge.

Alice has $$$M$$$ fair dice, with $$$A_1, A_2, \dots, A_M$$$ sides. For all integers $$$k$$$ and $$$l$$$ such that $$$1 \leq k \leq M$$$ and $$$1 \leq l \leq A_k$$$, the $$$k^\text{th}$$$ die of Alice has a probability $$$1/A_k$$$ of showing its face numbered $$$l$$$. Then, Alice's score is the sum of the numbers displayed by her $$$M$$$ dice. Similarly, Bob has $$$N$$$ fair dice, with $$$B_1, B_2, \dots, B_N$$$ sides.

Given these dice, Alice has a probability $$$\mathbb{P}_A$$$ of having a strictly larger score than Bob, and Bob has a probability $$$\mathbb{P}_B$$$ of having a strictly larger score than Alice. Which probability is the largest one?

Freshly arrived on the market, retailer YAOGS (Yet Another Olympic Goodies Seller) sells very expensive Olympics-themed items. To make themselves better known to the public, they half-heartedly decide to give away some of these items via a contest: the first person to answer correctly the question "How many circles are there in the Olympic Games logo?" can thus gain up to $$$P$$$ very expensive but equally valued items.

To spice things up (and spend less), YAOGS however opts for an additional challenge, as follows. The $$$P$$$ available items are positioned along some, but possibly not all of the alleys of YAOGS's headquarters; each alley can thus contain 0, 1, or more items. For reasons unknown, these alleys form a connected, undirected, acyclic graph (i.e., a tree) with $$$N$$$ nodes, numbered from 0 to $$$N-1$$$.

The winner knows $$$N$$$ but has no idea about either the tree structure or the items' placement. Once goodies are placed, her task is to choose a start node $$$m$$$ and an end node $$$n$$$. She can then collect all the items on the (unique) path from $$$m$$$ to $$$n$$$ in the tree.

YAOGS decides to cleverly place the goodies so that they minimise the maximum number of items that can possibly be collected. Assuming they properly carry out this task, what is the maximum number of items the winner can collect?

Two team leaders get to assemble their teams by choosing team members among a set of players that are numbered from 1 to $$$N$$$. The leaders take turns, each picking the $$$k^\text{th}$$$ player among the remaining ones, according to their ideas of which one of the remaining players would be the best addition to their teams.

Given the choices of the two leaders (the first team leader starts first), please compute the list of players in each team.

Coming back home after triumphally winning your long-coveted trophy, you discover that it was shattered to pieces in your trunk. It just remains to repair it.

Your trophy had the shape of a rectangle of size $$$3 \times N$$$, for some integer $$$N \geq 1$$$, thereby consisting of 3 lines and $$$N$$$ columns, containing a total of $$$3N$$$ unit squares. It was broken into $$$K$$$ pieces, the $$$k^\text{th}$$$ piece being a rectangle of size $$$A_k ×\times B_k$$$ for some integers $$$A_k$$$ and $$$B_k$$$ such that $$$1 \leq A_k \leq B_k \leq 3$$$. Such pieces may have been rotated, or even flipped, in the havoc that is your trunk.

As the first step towards repairing your trophy, you should reassemble them in the form of a rectangle of size $$$3 \times N$$$. More precisely, you have drawn, on a sheet of paper, a $$$3 \times N$$$ rectangle on which you will place your $$$K$$$ pieces, and you need to know, for all integers $$$i \leq 3$$$ and $$$j \leq N$$$, which piece will cover the unit square on the $$$i^\text{th}$$$ line and $$$j^\text{th}$$$ column of your rectangle.

The opening ceremony for the Olympic Games will take place on the river with teams on boats. The layout of the athletes on top of the boat has been designed in a very specific way: for each team, the $$$N$$$ athletes (conveniently numbered from 1 to $$$N$$$) are arranged as a binary tree.

The organiser has also designed the pre-order traversal, post-order traversal, and a (possibly empty) consecutive part of the in-order traversal of the binary tree that each team must follow.

Now, to make sure there are enough tree layouts so that each team can have a distinct one, you are asked to calculate the quantity of different possible in-order traversals, say $$$T$$$, modulo the prime number $$$999~999~937$$$.