Alice and Bob are playing a game!

Alice and Bob both knows some string $$$S$$$ of length $$$N+1$$$ that consists of only the characters A and B. The game is played on a $$$(N+1) \times (N+1)$$$ matrix, with rows and columns numbered from $$$0$$$ to $$$N$$$. We denote the cell in row $$$i$$$ and column $$$j$$$ as $$$(i, j)$$$.

Initially, a token is placed on $$$(0, 0)$$$. Each turn,

• Suppose the token is on cell $$$(i, j)$$$. The turn player must move the token to either $$$(i+1, j)$$$ or $$$(i, j+1)$$$.

The game ends when the token reaches the anti-diagonal of the matrix, which is the set of cells $$$\{(i, j) \mid i + j = N\}$$$. In other words, there will be a total of $$$N$$$ turns in the game. The winner of the game is determined by the string $$$S$$$:

• If the token ends on the anti-diagonal cell $$$(i, N - i)$$$, and $$$S_i = \texttt{A}$$$, then Alice wins.
• If the token ends on the anti-diagonal cell $$$(i, N - i)$$$, and $$$S_i = \texttt{B}$$$, then Bob wins.

Alice moves first. Among the $$$2^{N+1}$$$ possible strings $$$S$$$, how many strings are there such that Alice wins the game, assuming both players play optimally? Since the answer can be very large, output the answer modulo $$$10^9 + 3233$$$.

Mashiro has a tree with $$$N$$$ vertices and $$$N - 1$$$ unweighted edges. It is known that any two vertices in the tree are connected.

Mashiro wants to perform a Morfonication on the tree. To put it simply, Mashiro will do several operations to transform the original tree to a new tree to her liking. Each operation Mashiro does is of the following:

• Select an edge from the tree and remove it. After this step, the tree becomes disconnected to two components.
• Add an edge between any two vertices such that the structure is reconnected into a tree.

Mashiro has came back from practice and she wants to know the exact operations of the Morfonication. Can you show her the operations to do so in the least number of operations possible?

In Piplup Nation, they are under attack by a horde of Chimchars. The battlefield can be represented by a line with $$$N$$$ areas labeled $$$1$$$ to $$$N$$$ from left to right.

There are $$$N$$$ Chimchars, with the $$$i^{\text{th}}$$$ Chimchar currently at area $$$i$$$ and having $$$H_i$$$ health remaining.

To defend the nation, there are $$$N$$$ Piplups, with the $$$i^{\text{th}}$$$ Piplup stationed at area $$$i$$$. Each Piplup can unleash a powerful Hydro Pump leftward, damaging Chimchars that are on its left (including its own area). Notably, the $$$i^{\text{th}}$$$ Piplup can fire a Hydro Pump that deals $$$D_i$$$ damage to all Chimchars in area $$$j \leq i$$$. However, each Chimchar only takes $$$\min (H, D_i)$$$ damage from the attack, where $$$H$$$ is the current health of the Chimchar.

Since Hydro Pump is a very powerful move, it has low PP, and each Piplup can only fire it once. Additionally, due to its low accuracy, the $$$i^{\text{th}}$$$ Piplup requires a certain number of X-Accuracy items, costing $$$C_i$$$, to successfully launch the attack.

As the commander of the Piplup army, your goal is to maximize the following value: $$$$$$(\text{Total damage dealt to Chimchars}) - (\text{Total cost})$$$$$$

SoCCat has a string $$$S$$$ consisting of lowercase English letters a to z. For their Final Year Project, SoCCat is interested in the so-called double string.

Formally, a string $$$T$$$ is a double string if and only if:

• $$$T$$$ has even length.
• The first half of $$$T$$$ is equal to the second half of $$$T$$$. In other words, $$$T_i = T_{i + \frac{|T|}{2}}$$$ for all $$$1 \leq i \leq \frac{|T|}{2}$$$.

Help SoCCat count the number of pairs of indices $$$(i, j)$$$ such that $$$1 \leq i \lt j \leq |S|$$$ and the substring $$$S[i, j] = S_i S_{i+1} \dots S_{j}$$$ is a double string!

The 2025 Pokemon Association Presidential Elections have just concluded! There were $$$N$$$ candidates running for the position of president, and $$$M$$$ votes were recieved. Each vote $$$i$$$ is a ranking of the $$$N$$$ candidates, which is a permutation $$$p_{i,1}, p_{i,2}, \dots, p_{i,N}$$$ of the integers from $$$1$$$ to $$$N$$$, with $$$p_{i, 1}$$$ ranked the highest, followed by $$$p_{i, 2}$$$, and so on, until the lowest ranked $$$p_{i, N}$$$.

Selina is in charge of tallying the votes. However, when she checked the list of voters, she realised that there were supposed to be $$$K$$$ voters, not $$$M$$$ voters! In other words, some voters may have submitted more than one vote, some may have not voted, or some non-voters may have somehow cast their vote. Selina does not want to redo the election due to suspicions in legitimacy of the votes, so she decided to forge $$$K$$$ votes to replace the $$$M$$$ votes recieved. However, the $$$K$$$ votes should not be too suspicious.

After some deliberation, she decided that if the $$$K$$$ votes satisfy the following condition, then they are probably not too suspicious:

For all integers $$$1 \leq t \leq K$$$, $$$1 \leq l \leq N$$$, if a candidate appears in the highest $$$l$$$ ranks in at least $$$\left \lceil \frac{t \cdot M}{K} \right \rceil$$$ of the $$$M$$$ received votes, then he/she should appear in the highest $$$l$$$ ranks in at least $$$t$$$ of the $$$K$$$ forged votes.

Selina proved non-constructively that she can always forge $$$K$$$ such votes regardless of the $$$M$$$ votes she recieves. However, she does not know how to actually forge these $$$K$$$ votes. Please help Selina with her forgery!

You are playing a game against SoCCat!

The game is played on a directed graph $$$G = (V, E)$$$ with $$$N$$$ vertices, numbered from $$$1$$$ to $$$N$$$. We denote $$$(u \to v)$$$ as a directed edge from vertex $$$u$$$ to vertex $$$v$$$. We denote $$$N(u)$$$ as the set of vertices such that there is an edge from $$$u$$$ to the vertices in $$$N(u)$$$. In other words, $$$N(u) = \{v \mid (u \to v) \in E\}$$$.

Initially, a token is placed on some vertex $$$S$$$, and the game score is $$$0$$$. Each turn,

• Suppose the token is on vertex $$$u$$$.
• If $$$|N(u)| = 0$$$, the game ends.
• If $$$|N(u)| = 1$$$, the token moves to the only vertex in $$$N(u)$$$. The game score increases by $$$1$$$.
• If $$$|N(u)| \geq 2$$$, you must choose two different vertices $$$v_1, v_2 \in N(u)$$$ such that $$$v_1 \neq v_2$$$. Then, SoCCat can choose to either move the token to $$$v_1$$$ or $$$v_2$$$. The game score increases by $$$1$$$.

You would like to play the game as long as possible, so you want to maximize the game score. SoCCat would like to end the game as soon as possible, so they want to minimize the game score.

Assuming both you and SoCCat play optimally, what is the maximum game score you can achieve? If the game can be played indefinitely, output -1. Otherwise, output the maximum game score.

Compute the above for all $$$S$$$ from $$$1$$$ to $$$N$$$!

Eevee recently learned that its name is a palindrome! This means that it reads the same forward and backward.

However, Eevee is sad to discover that not many words are palindromes. One day, Eevee was visited by a friend. Upon hearing the friend's name, Eevee became curious.

Eevee wondered how many different ways there are to remove a single character from the friend's name so that the remaining characters, when concatenated, form a palindrome.

For example, in eevaee, removing either v or a is valid, but removing any of the e's is not.

We define a palindrome as the following: Given a string $$$S = s_1s_2\dots s_n$$$, we pair $$$(s_1, s_n)$$$, $$$(s_2, s_{n-1})$$$, $$$\dots$$$, $$$(s_{\lfloor \frac{n}{2}\rfloor}, s_{\lfloor \frac{n}{2}\rfloor + 1})$$$. $$$S$$$ is a palindrome if and only if in all of these $$$\lfloor \frac{n}{2}\rfloor$$$ pairs the characters in the pairs are identical.

Along Seabreak Path, there are $$$N = 3^K$$$ rows of flowers, with each row containing exactly $$$K$$$ flowers. In the $$$i$$$-th row ($$$0 \leq i \leq N - 1$$$), the color of the flowers is denoted by the ternary representation of $$$i$$$, with $$$0$$$ representing red, $$$1$$$ representing green, and $$$2$$$ representing blue.

E.g., if $$$K = 4$$$ and $$$i = 38 = 1102_{3}$$$. Then, the flowers in the $$$38$$$th ($$$0$$$-indexed) row are green, green, red, and blue, in that order.

Shaymin likes each row of flowers a different amount, so they assign a beauty value $$$B_{i}$$$ to each row, where $$$B$$$ is a permutation from $$$0$$$ to $$$N - 1$$$.

Two rows $$$i$$$ and $$$j$$$ are considered independent if they do not have any identical flowers in the same column.

E.g., row $$$i = 3 = 0010_{3}$$$ and row $$$j = 38 = 1102_{3}$$$ are independent, while row $$$i = 3 = 0010_{3}$$$ and row $$$j = 22 = 0211_{3}$$$ are not independent because the first flowers are both red, and the third flowers are both green.

Two rows $$$i$$$ and $$$j$$$ are considered an independent inversion if:

• $$$i \lt j$$$
• $$$B_{i} \gt B_{j}$$$
• Rows $$$i$$$ and $$$j$$$ are independent.

Help Shaymin count the number of independent inversions in Seabreak Path!

Recently, a new company, Hyper Flex Technologies, decided to sponsor Prof. Halim's CS3233 course and, as a result, received a large influx of applicants.

An interview was held to evaluate candidates for leadership abilities. Candidates enter the room one by one, in increasing order of skill level $$$A_i$$$, and form a line in the room.

When a new candidate arrives, they must partition the existing candidates into contiguous groups. The rightmost (newest) candidate picks their own group first. Then, the next rightmost ungrouped candidate becomes the new leader and picks their group, continuing until all candidates are grouped.

Each group contributes a conflict factor to the total score:

$$$$$$\text{conflict factor} = (\max A - \min A) \times (\text{group size}) + C$$$$$$

where $$$C$$$ is a constant, known as the chaos index. The new candidate's score, $$$S_i$$$, is the sum of all conflict factors across groups, and their goal is to minimize their score.

The interviewers maintain a list of potential candidates in front of the interview room. After the $$$i$$$-th candidate is scored, they compute:

$$$$$$B_i = ((S_i + K_i) \bmod i) + 1$$$$$$

and modify the list accordingly. Specifically, the $$$B_i$$$-th candidate (1-indexed) is either added to or removed from the list: if the candidate is already on the list, they are removed; otherwise, they are added. (No one really knows how the interviewers judge candidates. But this is the blackbox pattern observed.)

Before entering the room, each candidate checks the list and avoids selecting leaders from it. Specifically, a candidate $$$i$$$ will not choose a group of the form $$$[j+1, j+2, \dots, i-1, i]$$$ if candidate $$$j$$$ is on the list. Since the list is only viewed before entering the room and they do not know the updated list, different candidates may have different sets of people they avoid when choosing their group during the partition process. (See sample explanation for better understanding.)

You are the last candidate — clearly the best — and you are anxious to know in advance what your score will be.

Red is a Pokemon trainer who has beaten the Kanto Pokemon League, and wants to get to Johto for new challenges. To get there, he needs to travel by train.

The region has $$$N$$$ train stations labelled from $$$1$$$ to $$$N$$$. Ash starts at station $$$1$$$ and needs to get to station $$$N$$$ to enter Johto. There are $$$M$$$ bidirectional train lines, where the $$$i^{\text{th}}$$$ train line connects stations $$$X_i$$$ and $$$Y_i$$$, and multiple train lines may connect the same pair of cities. It is possible to get from city $$$1$$$ to city $$$N$$$ with the train lines, but it may not be possible to get from city $$$1$$$ to some other cities with the train lines.

To use the $$$i^{\text{th}}$$$ train line, Red needs to pay $$$C_i$$$ dollars for a lifetime pass, after which he may use the train line as many times as he wants. He can only purchase the pass for the $$$i^{\text{th}}$$$ train line when he is at station $$$X_i$$$ or $$$Y_i$$$, and he can only purchase it once.

The payment system is online, where Red only needs to make a delayed bulk payment for the passes he bought when he enters Johto (due to immigration policies). Note that when he reaches station $$$N$$$, he does not need to pay yet, and can continue taking trains. He only pays when he exits station $$$N$$$ and reaches the immigration counter.

Due to a bug in the system, he will only need to pay for the passes with the $$$K$$$ smallest costs (or all of them if he bought fewer than $$$K$$$ passes) when he reaches Johto.

Help Red determine the minimum amount of money (in dollars) he needs to spend to get from Kanto to Johto.

In the 2025 Pokeathlon World Cup, the clock ticks into the 90th minute. The stadium is deafening, the tension is unbearable—Team Pingu is locked in a dead heat with their rivals. The ball is at the feet of their captain, the indomitable Piplup. He eyes the goal, calculating the perfect shot. The crowd holds its breath. He takes aim—AND STRIKES! The ball rockets forward, slicing through the air like a missile. Time slows as it hurtles toward the net… AND IT'S IN! GOOOOOOAL! The fans erupt in wild celebration as Piplup delivers the match-winning strike!

The goal area can be treated as a rectangle with walls on three of its sides. Since Piplup is incredibly strong, the ball will not lose speed upon hitting the sides of the goal but will instead perfectly reflect off the walls. You are tasked with capturing a photo of this incredible match-winning shot. To get the perfect image, you plan to stand just behind the goal. However, you are afraid that the ball might hit your $100,000 camera. Thus, you must calculate where the ball will impact the back wall of the goal so that you can position yourself as far away as possible while still being directly behind the wall.

You are given the location where Piplup made the shot and the point at which he was aiming. (The aiming point may be behind the goal.) Note that it is guaranteed that the ball, following a straight line, will go into the goal and eventually hit the back wall. (As Piplup had secretly used the move Lock-On prior to taking the shot.) Please determine the farthest distance from any point on the back wall to the point where the ball will hit the back wall of the goal. (Please refer to sample explanation for a clearer picture.)

Tomori is playing a minigame at a card shop. In the game, there are $$$N+1$$$ cards numbered from $$$0$$$ to $$$N$$$, with each number appearing on exactly one card. The game works as follows: the player chooses one card, and then the shop rewards the player with a card whose number is equal to the bitwise XOR of the numbers on the $$$N$$$ cards that were not chosen.

Since Tomori already owns all the cards numbered from $$$0$$$ to $$$N$$$, she wants to obtain a card with a number greater than $$$N$$$ — that is, a card she doesn't already have.

For example, when $$$N = 12$$$, Tomori can choose the card numbered $$$3$$$ and she will win the card numbered $$$0 \texttt{XOR} 1 \texttt{XOR} 2 \texttt{XOR} 4 \texttt{XOR} \dots \texttt{XOR} 12 = 15$$$, a card she doesn't already have.

However, she realizes that for some values of $$$N$$$ it is impossible to win such a card. To avoid wasting time and money, she wants to know in advance whether her goal is achievable for a given $$$N$$$. Help her determine that!