You're given an integer $$$m$$$ and a sequence of integers $$$z_1,\dots,z_n$$$.

For each $$$z_i$$$, calculate the number of integers $$$x$$$, $$$y$$$ ($$$0 \leq x, y \lt m$$$) such that $$$$$$ x^2 + y^2 \equiv z_i \pmod m. $$$$$$

Super Meat Bros is a manga about two brothers Meatio and Meatigi who ultimately love meat.

Signature feature of this manga is that both brothers have their own story arcs that progress independently. Each brother will have a story of zero or more arcs, each arc containing at most $$$n$$$ manga issues. For an arc that would last $$$k$$$ issues, the mangaka knows $$$a_k$$$ ways to make a story about Meatio and $$$b_k$$$ ways to make a story about Meatigi.

The mangaka will make two stories, one about Meatio and the other about Meatigi. The story about Meatio is created in the following way: Until the mangaka is bored, they choose a number $$$k \le n$$$ and append a new story arc of $$$k$$$ issues to the story in one of $$$a_k$$$ distinct ways. Correspondingly, for Meatigi story, the mangaka chooses $$$k$$$ and appends a new story arc of $$$k$$$ issues in one of $$$b_k$$$ distinct ways.

After full stories of several arcs are prepared for both Meatio and Meatigi, they will be merged together in a way that preserves internal order of stories. That is, if issues $$$x$$$ and $$$y$$$ are related to the same brother and in his story $$$x$$$ comes before $$$y$$$, it will also come before $$$y$$$ in the merged story. Other than that merging can be arbitrary, in particular story arcs do not have to form a contiguous subsequence.

You're given $$$a_1, \dots, a_n$$$ and $$$b_1, \dots, b_n$$$, calculate the number of ways to create a full volume of $$$m$$$ issues.

You wake up in an unfamiliar room and a robotic voice greets you. You're in trouble.

The voice explains that you're being a subject of an ethically questionable series of experiments. The test you're undergoing right now goes as follows. An AI picked an integer number from $$$1$$$ to $$$n$$$ in such a way that the number $$$k$$$ had a probability $$$\frac{p_k}{p_1+\dots+p_n}$$$ to be picked. You need to guess the number.

If you guess it incorrectly, you'll be put to sleep, your memory will be erased and you will undergo the same test again. With a probability of $$$c$$$ percent, the number chosen by the AI will be re-picked by the same procedure and with a probability of $$$100-c$$$ percent, it will stay the same.

You have no idea how many times you already participated in this test and what numbers you have picked before, but you clearly want to spend as little time on it as possible. Therefore, you will choose a probability distribution $$$q_1, \dots, q_n$$$ and will say the number $$$k$$$ with the probability $$$q_k$$$.

What is the minimum expected number of guesses you need to make before completing the test?

Let $$$b_1, b_2, \dots, b_{n}$$$ be a sequence of integers. A sequence of polynomials $$$A_1,A_2,\dots,A_n$$$ is defined as

$$$$$$ A_k(x) = \det \begin{bmatrix} x & b_1 & 0 & \dots & 0 \\ 1 & x & b_2 & \dots & 0 \\ 0 & 1 & x & \cdot & \vdots \\ \vdots & \vdots & \cdot & \ddots & b_{k} \\ 0 & 0 & \dots & 1 & x \end{bmatrix} $$$$$$

We call $$$b_1, b_2, \dots, b_{n}$$$ good if for all $$$k$$$, all coefficients of $$$A_k$$$ do not exceed $$$1$$$ by the absolute value.

You're given a sequence $$$c_1,c_2,\dots,c_n$$$ such that $$$c_k \in\{-1,1\}$$$. You can change any number $$$c_k$$$ to $$$-c_k$$$.

What is the minimum numbers of the sequence elements you should change to get a good sequence?

There are $$$10^9$$$ types of garbage and $$$10^9$$$ types of garbage bins in your country. You are only allowed to dispose garbage of type $$$x$$$ into a garbage bin of type $$$y$$$ if $$$\gcd(x, y)=1$$$, where $$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

In your neighborhood, only garbage of type $$$L \leq x \leq R$$$ ever occurs, and there are only garbage bins of types $$$L \leq y \leq R$$$ available. To avoid overflowing the bins, you want to throw each piece into distinct bin. Given $$$L$$$ and $$$R$$$, find a valid distribution or report that it does not exist.

A palindromic polynomial is a non-zero polynomial whose coefficients read the same in both directions.

Alan had a palindromic polynomial $$$A$$$ of a degree $$$d \le 10^4$$$. He wrote down its values modulo $$$10^9+9$$$ in $$$n$$$ distinct integer points. Then he lost the polynomial. Now he wants to restore it from the points. Help Alan find any palindromic polynomial of degree at most $$$10^4$$$ which passes through all given points.

Formally, you are given a list of pairs $$$(x_1, y_1), (x_2, y_2) \dots (x_n, y_n)$$$, $$$0 \le x_i, y_i \lt 10^9+9$$$. Your task is to find any polynomial $$$A(x) = a_d x^d + a_{d-1} x^{d-1} + \dots + a_1 x + a_0$$$, such that:

• $$$0 \le d \le 10^4$$$ and $$$a_d \neq 0$$$;
• $$$0 \le a_i \lt 10^9+9$$$ for $$$i=0 \dots d$$$;
• $$$A(x_i) \equiv y_i ~(\text{mod}~ 10^9+9)$$$ for $$$i=1\dots n$$$;
• $$$a_i = a_{d-i}$$$ for $$$i=0\dots d$$$.

For an array $$$a=[a_1, a_2, \dots, a_n]$$$, $$$n \ge 2$$$, its difference array is defined as $$$[a_2-a_1, a_3 -a_2, \dots, a_n-a_{n-1}]$$$.

The array $$$a=[a_1, a_2, \dots, a_n]$$$ is a palindrome if it doesn't change after being reversed.

A permutation of array $$$a$$$ is an array which has the same elements as $$$a$$$, but possibly in a different order.

You are given an array $$$a$$$ of length $$$n$$$. Find the number of distinct permutations of $$$a$$$ whose difference array is a palindrome. Two arrays $$$a$$$ and $$$b$$$ of same length are distinct if and only if for some $$$i$$$, $$$a_i \ne b_i$$$.

As this number can be very large, print it modulo $$$10^9+9$$$.

Two undirected graphs with $$$n$$$ vertices $$$G_1$$$ and $$$G_2$$$ are called isomorphic if there is a permutation $$$p_1, p_2, \dots, p_n$$$, such that

$$$$$$ (u, v)\text{ is an edge of }G_1 \iff (p_u, p_v)\text{ is an edge of }G_2 $$$$$$

Given an undirected graph $$$G$$$, you should determine whether it is true that there are no more than $$$n$$$ distinct graphs that are isomorphic to $$$G$$$.

Two undirected graphs with the same number of vertices are considered distinct if their sets of edges are distinct.

To generate a directed acyclic graph (DAG), we start with an empty set $$$A$$$ of the DAG vertices and the set $$$B=\{1,2,...,n\}$$$ of candidate vertices.

Then, we add vertices to the DAG one by one in the following manner:

1. We pick a set $$$X \subseteq A$$$ and a vertex $$$u \in B$$$ uniformly at random;
2. We draw arcs from all vertices of $$$X$$$ into $$$u$$$;
3. We add $$$u$$$ to $$$A$$$, and remove $$$u$$$ from $$$B$$$.

In the end, we get a DAG on $$$n$$$ vertices. We used this procedure twice and generated two DAGs on $$$n$$$ vertices. What is the probability that they are distinct?

Two DAGs are considered distinct if their sets of directed edges are distinct.

Prince of Persia walks into a casino holding the dagger of time...

Initially he has a single gold coin. He goes to a roulette and starts betting. On each bet he chooses between red and black and must bet a positive integer amount of coins on it. If he wins, he gets double his bet back. Otherwise he loses the bet. Roulette outcomes are distributed uniformly (i.e. both red and black have probability of $$$\frac{1}{2}$$$) and independently from each other.

After the roulette outcome is known, Prince may rollback to the point in time immediately before he made the bet and redo it in any way he wants (possibly betting on a different color or betting a different amount of coins). The roulette outcome will not change after doing rollback. Prince wants to make a total of $$$n$$$ bets and he may use the rollback at most $$$m$$$ times throughout them. Rolling back and redoing a bet does not count as making a new bet.

Prince wants to make sure that before each of $$$n$$$ bets he has at least $$$1$$$ coin in his possession to make a valid bet, while otherwise maximizing the expected amount of coins he will leave with. Given $$$n$$$ and $$$m$$$, determine the expected amount of coins Prince would leave with. If it's not possible to guarantee that Prince makes a sequence of $$$n$$$ valid bets, print bankrupt instead.

You're given an array $$$a_0, a_1, \dots, a_{2^n-1}$$$.

Consider a $$$2^n \times 2^n$$$ matrix $$$A$$$ such that $$$A_{ij} = a_{i | j}$$$, where $$$i | j$$$ is the bitwise OR of the numbers $$$i$$$ and $$$j$$$.

Find the determinant of $$$A$$$.

You are given integers $$$n$$$ and $$$m$$$.

Count the number of directed graphs $$$G$$$ without loops and multiple edges that satisfy all of the following:

• $$$G$$$ contains exactly $$$n$$$ vertices, labeled $$$1, \ldots, n$$$.
• Every vertex lies on at most one simple cycle.
• There are exactly $$$m$$$ edges that do not belong to any cycle.

Two graphs are considered different if there exist vertices with labels $$$u$$$ and $$$v$$$ such that the edge $$$u \to v$$$ exists in one graph, but not the other.

A simple cycle is a directed cycle that visits each vertex at most once.

Siteswap (https://en.wikipedia.org/wiki/Siteswap) is a juggling notation that allows to represent juggling patterns.

In siteswap, it is assumed that throws happen by two alternating hands on beats that are equally spaced in time. A siteswap pattern is a sequence of numbers in which throws are represented by non-negative integers that specify the number of beats in the future after which the object is caught and thrown again.

In other words, a siteswap pattern is a sequence $$$a_1, a_2, \dots, a_n$$$, in which $$$a_k$$$ describes the throw made on the $$$k$$$-th beat and means that the object is caught and thrown again after $$$a_k$$$ seconds, that is, on the $$$(k+a_k)$$$-th second.

For example, the number $$$1$$$ means that the object is passed to the other hand to be thrown immediately on the next turn, and the number $$$2$$$ means that the next throw with the same hand happens with the same object. The special number $$$0$$$ in the pattern is used to denote that the hand is empty on the corresponding beat. See notes for more examples.

A siteswap pattern is valid if it can be repeated indefinitely in such way that each beat the current hand catches and then immediately throws at most one object.

For each valid pattern, it is possible to uniquely identify the number of objects needed to perform it. We may further classify these objects into those that eventually change the hand they're thrown with and those that do not. Given a valid siteswap pattern, find the number of objects that do not change the hand for each hand, and the number of objects that do change hand.