Busy Beaver has $$$N$$$ bins and a large amount of balls. The $$$i$$$-th bin can hold up to $$$s_i$$$ balls and currently contains $$$a_i$$$ balls. In a move, he first chooses a bin $$$i$$$ that is currently full (i.e., $$$a_i = s_i$$$). Then, for each ball in the chosen bin, he chooses to either discard it or move it to a different bin with enough space. (Within the same move, it is allowed to move different balls to different bins.)

Using only these moves, Busy Beaver is trying to remove all of the balls from all of the bins. Determine whether or not it is possible to do so.

Busy Beaver has just learned about the Median of Medians algorithm! To better understand the algorithm, he has chosen an odd positive integer $$$N$$$ and wants to experiment with permutations of $$$\{1,2,\dots,3N\}$$$.$$$^{\text{∗}}$$$

For any odd number $$$k$$$ and a sequence of distinct numbers $$$A = (a_1,a_2,\dots,a_k)$$$, let $$$B = (b_1,b_2,\dots,b_k)$$$ be $$$A$$$ sorted in increasing order. Then, $$$\text{median}(a_1,a_2,\dots,a_k)$$$ is $$$b_{\frac{k+1}{2}}$$$, the $$$\left(\frac{k+1}{2}\right)$$$-th element of $$$B$$$.

Busy Beaver thinks that a permutation of $$$(p_1,p_2,\dots,p_{3N})$$$ of $$$\{1,2,\dots,3N\}$$$ is nice if and only if

$$$$$$ \text{median}\Big(\text{median}(p_1, p_2, \dots, p_N),\text{median}(p_{N+1}, p_{N+2},\dots,p_{2N}),\text{median}(p_{2N+1},\dots,p_{3N})\Big) = \frac{3N+1}{2}. $$$$$$

Busy Beaver is extra picky with his permutations; he likes having certain numbers in certain positions. He has $$$M$$$ pairs of numbers $$$(a_i,b_i)$$$. A nice permutation $$$(p_1,p_2,\dots,p_{3N})$$$ is fitting if $$$p_{a_i} = b_i$$$ for all $$$1 \leq i \leq M$$$.

Help Busy Beaver determine the number of fitting permutations! Since the number of such permutations may be very large, compute the number of such permutations modulo $$$10^9 + 7$$$.

There are four subtasks for this problem.

• ($$$10$$$ points): $$$N \leq 3, T \leq 10$$$.
• ($$$25$$$ points): $$$N \leq 10^3$$$.
• ($$$20$$$ points): $$$M = 0$$$.
• ($$$45$$$ points): No additional constraints.

Busy Beaver is taking a walk on a path of colorful tiles.

The path consists of a line of $$$N$$$ tiles, each colored either red (r), green (g), blue (b), or yellow (y).

Busy Beaver's walk will follow these rules:

• The walk visits $$$N$$$ tiles, starting from any initial tile.
• Each move must be to a tile at most two positions away from the current tile (possibly revisiting a previously visited tile, going backwards, or staying at the same tile).

Busy Beaver will record the sequence of tile colors he visits on the walk in order. Busy Beaver is confident that he can recreate any sequence of $$$N$$$ colors on his walk.

Prove him wrong by providing any sequence of $$$N$$$ colors he can't recreate.

It can be shown that an answer always exists.

There are three subtasks for this problem.

• ($$$10$$$ points): $$$N \leq 10, T \leq 10^3$$$.
• ($$$10$$$ points): $$$N \leq 100, T \leq 10^3$$$.
• ($$$80$$$ points): No additional constraints.

While studying for his algorithms midterm, Busy Beaver came up with the following problem and wants your help to solve it.

You are given an integer $$$N$$$ and a permutation $$$p_1,p_2,\ldots,p_N$$$ of length $$$N$$$.$$$^{\text{∗}}$$$ Find the length of the longest contiguous subarray ($$$l,r$$$) ($$$1 \le l \le r \le N$$$) of $$$p$$$ such that the number of inversions$$$^{\text{†}}$$$ of $$$p_l,p_{l+1},\ldots,p_r$$$ is not divisible by $$$K$$$, or determine if such a subarray does not exist.

Help Busy Beaver find the answer to this problem!

There are two subtasks for this problem.

• ($$$10$$$ points): The sum of $$$N$$$ across all test cases is no more than $$$2 \cdot 10^3$$$.
• ($$$90$$$ points): No additional constraints.

Let $$$K$$$, $$$P$$$, and $$$X$$$ be integers, where $$$P$$$ is prime and $$$0 \le K \le \min(P-1, 8)$$$.

Define a sequence $$$a$$$ of rational numbers as follows:

• $$$a_1 = 1$$$.
• For all $$$n \ge 2$$$, $$$a_n = X \sum_{i=1}^{n-1} \frac{a_i}{n-i}$$$.

Output $$$a_{P-K}$$$ modulo $$$P$$$ (note the unusual modulo). Formally, let $$$a_{P-K} = \frac{x}{y}$$$ in lowest terms, and output an integer $$$0 \le b \lt P$$$ such that $$$by \equiv x \pmod{P}$$$. We can show that such a $$$b$$$ exists and is unique under the constraints of this problem.

We recommend that C++ users use the following code, from KACTL, to perform modulo operations faster. Note that creating FastMod instances is a relatively slow operation, so avoid repeatedly doing so for the same modulo.

typedef unsigned long long ull;
struct FastMod {
	ull b, m;
	FastMod(ull b) : b(b), m(-1ULL / b) {}
	ull reduce(ull a) {
		ull q = (ull)((__uint128_t(m) * a) >> 64), r = a - q * b;
		return r - (r >= b) * b;
	}
};

• ($$$25$$$ points): The sum of $$$P$$$ over all test cases does not exceed $$$10^5$$$.
• ($$$75$$$ points): No additional constraints.