Kevin loves his Pokemon memes and he thinks he has come up with an especially good one. He posts it into his Pokemon Showdown discord server and adds a single eye emoji react to hopefully start the chain of reacts.

Due to the high volume of traffic in the server, the reacts to his posts only update at the end of the day and he finds that every night, the number of reacts on his post doubles. He can also add a react to his post every morning and it will update immediately since it is his own post. Kevin wants exactly $$$n$$$ reacts on his post and being a lazy competitive programmer, he wants to react to his own post as few times as possible and still get the exact number of $$$n$$$ reacts.

Help Kevin figure out the minimum number of times he must react to his own post (including the first time he reacts to his post when he posted the meme) in order to have exactly $$$n$$$ reacts.

Often, when Aditya writes problems, he gets caught up in making sure that his solution is valid using a series of proofs. He has $$$n$$$ different propositions to consider, with labels from $$$1$$$ to $$$n$$$. He has $$$m$$$ implications proved already, where an implication is defined as a pair $$$(u , v)$$$, which means that if proposition $$$u$$$ is true, then proposition $$$v$$$ is also true. Note that you can combine implications to create new implications; for example if you have $$$(u, v)$$$ and $$$(v, w)$$$, then you can also create the implication $$$(u, w)$$$. Aditya's goal is to construct all possible implications between the $$$n$$$ propositions, but he recognizes that this might take significant time. Instead, he will pick a starting proposition, $$$s$$$, and you must find the number of new implications involving $$$s$$$ (of the form $$$(s, u)$$$ or $$$(u, s)$$$ for arbitrary implication $$$u \neq s$$$) that are not already proved by the $$$m$$$ implications Aditya already has.

Kevin is trying to buy tacos for an upcoming UTPC contest! Since the club's budget is limited, he wants to spend the least possible money while also feeding all the attendees comfortably. Normally, this would simply entail going to Torchy's Tacos and buying the appropriate distribution of tacos, but today, Kevin has found a way to reduce the cost.

It turns out that there's a taco market right outside Torchy's! Lots of people have gathered around and are willing to make some trades. Specifically, for some tacos $$$i, j$$$, if you have one of taco $$$i$$$, you can exchange it for taco $$$j$$$ for a price $$$p_{i, j}$$$. While these trades may not be possible for all pairs of tacos, nor are they bidirectional, for the trades that do exist, you can do them an infinite amount of times.

Given the base prices of all the tacos as well as the prices of all these possible trades, Kevin now wants to find the lowest price to complete his order of tacos. Given that he can walk back and forth between each of the markets as well as to Torchy's itself, determine the minimum cost to acquire the desired distribution of tacos!

Back in the days when programming contests were held in person, team seating was often a great kerfuffle. Who will sit where? Is there enough room nearby for my entire team? Where is the nearest outlet? Can the opponents see my computer screen?!?

As competitors would sprawl out during the course of a contest in order to solve their problems, seat-hopping occurred practically every five minutes, and each competitor paid careful attention to precisely which chair she would try to move into, based on specific rules. Given a 2D map of the contest auditorium, with the locations of all chairs, competitors, and outlets, help simulate where the competitors of different teams will be located after a certain number of five-minute intervals!

Every five minutes, at the time of seat-hopping, each competitor will only attempt to move into an adjacent space in the contest auditorium if each of the following conditions is true...

1. If the space currently contains an empty chair, denoted '#'. This means that the space must not be empty without a chair, denoted by '.', and it must not have a chair with another competitor sitting on it, denoted by a lower-case letter uniquely identifying the team that that competitor belongs to.

2. If the chair is close enough to an outlet, denoted '*'. In order for a chair to be "close enough" to an outlet, the outlet must be within 3 cells of movement according to taxicab distance from the chair—meaning that, using only adjacent moves up/down/left/right through cells on the auditorium map, an outlet could be reached within 3 moves or less.

3. If the chair is not adjacent to where an opponent is sitting. If an opponent, meaning another competitor with a team name (denoted by a lower-case letter) different from this competitor's team name, is sitting adjacently to the empty chair, the competitor will not try to move into that chair because then their opponent might be able to steal answers!

4. If the space is the most preferred out of other viable, adjacent options. In the case where multiple adjacent chairs are eligible for the competitor to move into, according to the above rules, then the competitor will prefer to sit in the north adjacent chair first (above them on the map), then the chair to their west (left), then to their east (right), and lastly the southmost adjacent chair (below).

Once the competitor selects a viable adjacent chair to move into, if one exists, then at the time of seat-hopping, the competitor will try to move into the seat. However, if any other competitor (including one's team members) had a similar idea and is also trying to move into that same chair, both competitors will notice each other and decide to remain where they are currently seated, instead of race to the chair and fight over who gets to sit in it. It's simply common courtesy.

Problem-writers love coming up with incredibly specific, completely useless properties of an arrays of numbers that they want you to compute for them. Now, we can't have an ICPC tryout contest without one of those problems so here is an especially contrived example to compute:

For a given array $$$A$$$, define $$$\psi(A)$$$ as the number of ways to negate certain elements of $$$A$$$ such that the sum of the elements of $$$A$$$ is now $$$0$$$. For example, $$$\psi([1, 1]) = 2$$$ because you can negate the first element and the array will then be $$$[-1, 1]$$$ which has a sum of $$$0$$$ or you can negate the second element making the array $$$[1, -1]$$$ which also has a sum of $$$0$$$.

Given an array $$$A$$$ of $$$n$$$ positive integers, let $$$S$$$ be the set of all contiguous, non-empty subarrays of $$$A$$$ (aka all arrays of the form $$$a_i, a_{i+1}, \dots a_j$$$ where $$$1 \leq i \leq j \leq n$$$ where two subarrays are considered different if they start and/or end at different indices, even if the values within the subarray are the same), compute the sum of $$$\psi(x)$$$ for all $$$x \in S$$$ aka $$$\sum\limits_{x \in S}\psi(x)$$$.

Note this number may be very large, so print it modulo $$$10^9 + 7$$$.

Zorro is angry at Erik (see Xorro the Xorman from the previous contest) for making a mockery of him with the creation of Xorro. The original swashbuckler decides to teach Erik a lesson by making him solve a problem of his own making, or to face the wrath of his blade. Zorro despises bitwise operations, but he is quite the number theory connoisseur. He gives Erik three positive integers $$$N$$$, $$$K$$$, and $$$X$$$, and asks the inferior swordsman to tell him if it is possible to sum exactly $$$K$$$ integer powers of $$$X$$$ to $$$N$$$. Can you save Erik from a gruesome fate (he is quite bad at number theory problems)?

Luke likes math problems, so he has asked you to solve this problem.

Given a vector $$$\langle x,y \rangle$$$, what is the total number of nonempty sequences of vectors $$$\{a_i\}_{i=0}^n$$$ such that:

• $$$a_0 = \langle x,y \rangle$$$.
• $$$\forall i \gt 0, i \in \mathbb{Z}, ||a_i||_2 \lt ||a_{i-1}||_2$$$.
• $$$\forall i \gt 0, i \in \mathbb{Z}, ||a_i - a_{i-1}||_2 \lt \sqrt{2}$$$.
• All vectors in $$$\{a_i\}$$$ have only integer entries.

Moreover, he will give you $$$Q$$$ queries, and you need to output the answer for each of these $$$\mod 10^9 + 7$$$ (a prime).

Note that for vector $$$v$$$ of dimension $$$n$$$, $$$||v||_2 = \sqrt{\sum_{i=1}^n v_i^2}$$$.

Often, UTPC problem writers struggle to make the problem that they come up with match the particular theme of the week. For example, here is a problem that the UTPC officers found hard to fit inside this week's meta theme. You are given a 2D grid of numbers and want to find the highest value island that you can create out of this grid. You can create an island by picking an initial starting coordinate and taking all grid spaces such that there exists a path taking only cardinal directions with grid values that are only greater than or equal to the grid value at the initial starting coordinate. The value of the island is the grid value at the initial starting coordinate multiplied by the number of grid entries that the island covers. Can you find the maximum value island on the grid? If there are multiple islands with equal value, always take the one that covers more grid entries.

Generating data for contests is very tedious work, and Viraj often gets bored doing it. During his breaks, he surfs various subreddits for pictures of the floofiest doggos. He also likes to ask his friends, including the other UTPC officers, for pictures of their pets to sneak into the test data he generates for geometry problems. However, Viraj's recent requests have been left on read, and he is infuriated at the lack of responses. He decides to kidnap ALL of their pets and store them at a remote location until enough photos can be amassed (some may even be posted on Reddit for karma). However, being a man of honor, Viraj decides to allow the officers a chance to get their beloved pooches back by solving his latest contest problem.

In each test case, there are $$$N$$$ lattice points on the Cartesian Plane such that no three points are collinear. The officers must consider every possible subset of the $$$N$$$ points, calculate the number of points in the convex hull of that subset, and add the sizes of the hulls together. This sum modulo $$$10^9+7$$$ can be decoded into a set of coordinates indicating the pets' location. The only issue is that all the officers hate geometry, so you need to help them out!