Shaban is moving from Earth to Mars, where the laws of physics are a little unusual.

On Earth, when several weights are placed on the same side of a balance scale, their weights are added together. For example, weights $$$2$$$ and $$$5$$$ have total weight $$$2 + 5 = 7$$$.

On Mars, however, weights are multiplied instead of added. Thus weights $$$2$$$ and $$$5$$$ have total weight $$$2 \cdot 5 = 10$$$.

Shaban wants to take a collection of balance weights with positive integer values to Mars. For every vegetable whose weight is an integer from $$$1$$$ to $$$m$$$, inclusive, he must be able to determine its exact weight by placing a non-empty subset of his weights on the empty side of the balance. On Mars, this means that the product of the chosen weights must be equal to the vegetable's weight.

Multiple carried weights may have the same value.

Your task is to find the minimum number of weights Shaban needs to take.

While 3atori and Habbab battle it out in CS2 and PUBG, this problem is all yours.

You are given a string $$$s$$$ of length $$$n$$$ and an even integer $$$k$$$.

Consider the $$$n$$$ suffixes of $$$s$$$, one suffix for each starting position. Choose exactly $$$k$$$ of these suffixes. The score of the chosen set is the number of distinct non-empty strings $$$p$$$ such that $$$p$$$ is a prefix of at least $$$\frac{k}{2}$$$ chosen suffixes.

Compute the sum of scores over all ways to choose exactly $$$k$$$ suffixes. Since the answer can be large, print it modulo $$$10^9 + 7$$$.

As every contestant knows, the head of the 7asa7ees gang caused unforgettable chaos in HIAST CPC 2024.

Since that day, the 3ara3eer gang devoted their lives to stopping the 7asa7ees from causing more trouble for the contestants. They trained in secret rooms, guarded old archives, and watched every problemsetting meeting from the shadows.

This year, destiny brought them to the same table again.

The head of the 7asa7ees, Fofo, entered the problemsetting room with a calm smile, holding a mysterious scroll covered with strange symbols. With great confidence, Fofo suggested a 7as7ous problem.

The room became silent.

Bisseh, the head of the 3ara3eer, stood up and rejected the idea at once. The air grew heavy. Papers flew from the table. The lights flickered. Fofo's smile disappeared.

A battle began.

Bisseh fought bravely, but Fofo was a true 7as7oos. With terrifying speed, Fofo defeated Bisseh and left him fallen among the broken chairs of the problemsetting room.

Then Al-Coach Habbab stepped forward.

Everyone knew Al-Coach Habbab had strong muscles. He believed he could take revenge for his leader, and for a moment, even Fofo looked worried. Habbab charged forward, shaking the whole hall with every step.

But Fofo raised one hand and whispered the forbidden spell: $$$$$$\texttt{7as}$$$$$$

The spell struck Al-Coach Habbab directly, and he fell before reaching Fofo.

Far away, 3atori, Anous, and Moufless saw the sky turning dark above the battlefield. Without hesitation, they climbed aboard their Jamalocopter and went straight to the fight area.

What happened next was remembered as one of the wildest battles in problemsetting history. The Jamalocopter roared through smoke and lightning. Moufless held the route steady through the storm. Anous dodged cursed statements. 3atori broke through waves of 7as7ous energy. Fofo answered every attack with another spell, another trap, another impossible twist.

At last, 3atori was cornered. His strength was fading. Fofo prepared the final strike.

Just before everything ended, 3atori raised his hand and cast the ancient spell: $$$$$$\texttt{3rr}$$$$$$

The battlefield shook.

Fofo was defeated.

But the story did not end there.

Sneakily, the 3ambaloos entered the fight area while nobody was watching. They moved Fofo to the hospital, where he is now healing and preparing for another battle.

To be continued.

The next battle is coming, and only one spell can be written on your banner.

Habbab thinks that this problem is very easy, so are you going to be '3rrar' and run away from us without solving it, or 'lesa al-amana momkenah'?

You are given a binary array $$$a$$$ of length $$$n$$$, and $$$q$$$ queries. Each query provides a range $$$[l, r]$$$, corresponding to the subarray $$$b = a_l, a_{l+1}, \dots, a_r$$$ of length $$$m = r - l + 1$$$.

For each query, calculate the number of good cyclic shifts$$$^\dagger$$$ of $$$b$$$.

A binary array $$$c$$$ of length $$$m$$$ is considered good if the following process finishes with $$$x = 0$$$:

• Initially, set $$$x = 0$$$ and $$$i = 1$$$.
• If $$$c_i = 1$$$, replace $$$x$$$ by $$$1 - x$$$ and set $$$i := i + 1$$$.
• If $$$c_i = 0$$$, leave $$$x$$$ unchanged and set $$$i := i + 2$$$.
• The process stops when $$$i \gt m$$$.

$$$^\dagger$$$ A cyclic shift of $$$b$$$ is formed by moving its first $$$k$$$ elements to the end ($$$0 \le k \lt m$$$), resulting in the array $$$b_{k+1}, \dots, b_m, b_1, \dots, b_k$$$. All $$$m$$$ possible shifts are counted independently for each query, even if they result in identical arrays.

It is a well-known fact in the problemsetting room: Fofo absolutely despises trees, and Jamal harbors an intense hatred for grids. Naturally, the room was left in stunned silence when Fofo, with a mischievous grin, unexpectedly proposed a tree problem.

Before the ink could even dry, Jamal narrowed his eyes and hit him with a swift, merciless $$$\texttt{3rr}$$$.

"Project it onto a grid," Jamal demanded.

After a fierce clash of wills, a compromise was born. What lies before you is the ultimate cocktail of Jamal and Fofo's $$$\texttt{7as7aseh}$$$—a grid problem haunted by the ghost of a tree.

Consider an $$$n \times m$$$ grid. A path is a sequence of cells moving exclusively down or to the right, starting and ending at distinct positions. The length of a path is the total number of cells it traverses.

Your challenge is to survive their $$$\texttt{7as7aseh}$$$ by filling the grid with positive integers such that it satisfies one core property: for every path of length $$$L$$$, at least two cells along that path must contain values divisible by $$$L$$$.

If their combined trap is too strong and no such valid grid exists, report that it is impossible.

You are given a connected undirected graph with $$$n$$$ vertices. The vertices contain the values $$$1, 2, \ldots, n$$$, each value exactly once.

In one operation, you may choose an edge $$$(u, v)$$$ and swap the values on vertices $$$u$$$ and $$$v$$$ if and only if the two values differ by exactly $$$1$$$.

You are given the initial values $$$a_1, a_2, \ldots, a_n$$$ and the target values $$$b_1, b_2, \ldots, b_n$$$. Determine whether it is possible to obtain the target values after applying zero or more operations.

Note that the input and output sizes are large, so using fast I/O is recommended.

Anas has an array $$$a$$$ of an even length $$$n$$$. The array can be partitioned into $$$\frac{n}{2}$$$ pairs such that the two elements in every pair are opposites: one is equal to $$$x$$$ and the other is equal to $$$-x$$$.

Anas removes exactly one element from the array and gives the remaining $$$n-1$$$ elements to Shaban. Determine the value of the removed element.

The order of the remaining elements may be arbitrary.

You may reorder the elements of $$$a$$$ arbitrarily. Let $$$b$$$ be the array obtained after reordering. The array $$$w$$$ is not reordered: $$$w_i$$$ always belongs to position $$$i$$$.

A position $$$i$$$ ($$$1 \le i \le n$$$) is called good if $$$b_i \le i$$$. The score of $$$b$$$ is the sum of weights of all good positions. In other words, for every good position $$$i$$$, add $$$w_i$$$ to the score.

Find the maximum possible score.

You are given two strings $$$s$$$ and $$$t$$$. Initially, the current string is equal to $$$s$$$.

In one operation, you may do exactly one of the following:

• remove a non-empty prefix of the current string;
• remove a non-empty suffix of the current string;
• insert a non-empty string at any position of the current string, including before the first character or after the last character.

The inserted string may be chosen arbitrarily, and its length does not matter.

Find the minimum number of operations needed to make the current string equal to $$$t$$$.

You are given a tree with $$$n$$$ vertices. Vertex $$$i$$$ initially contains $$$a_i$$$ integer units of value.

For an edge $$$(u, v)$$$ with cost $$$w$$$, moving one unit of value from $$$u$$$ to $$$v$$$ costs $$$w$$$, and moving one unit from $$$v$$$ to $$$u$$$ also costs $$$w$$$. You may perform any number of such transfers. The final values of all vertices must be integers, and the total amount of value is preserved.

Let the final values be $$$b_1, b_2, \ldots, b_n$$$. Your primary goal is to minimize the difference between the maximum and minimum final values. Formally, you must minimize

$$$$$$\max(b_1, b_2, \dots, b_n) - \min(b_1, b_2, \dots, b_n)$$$$$$

Among all ways to obtain this minimum possible difference, find the minimum possible total transfer cost.

You are given an array $$$a_1, a_2, \ldots, a_n$$$ and an integer $$$k$$$.

For every subarray $$$[l,r]$$$ ($$$1 \le l \le r \le n$$$), define $$$$$$ f(l,r)=\left[\sum_{i=l}^{r-1} a_i \oplus a_{i+1}\right]-a_l \oplus a_r $$$$$$ Here $$$\oplus$$$ denotes the bitwise XOR operation. If $$$l=r$$$, the sum is empty and is defined to be $$$0$$$.

Count the number of subarrays $$$[l,r]$$$ such that $$$f(l,r)=k$$$.

While wandering through the desert, Ammar and his camel discover a sealed cave. A short chant opens the door, but there is still no water inside. Instead, Ammar finds the Bassami Water Puzzle.

The puzzle has an ordered box $$$v$$$. The box starts empty and can hold at most $$$m$$$ stones. Ammar then receives $$$n$$$ stones one by one.

The $$$i$$$-th stone is described by two values, $$$id_i$$$ and $$$state_i$$$:

• $$$id_i$$$ is the identifier written on the stone;
• $$$state_i=0$$$ means the stone is broken;
• $$$state_i=1$$$ means the stone is unbroken.

The same identifier may appear more than once in the input. The box, however, never contains two stones with the same identifier.

For each incoming stone, apply the first rule below that matches the current box:

1. A stone with identifier $$$id_i$$$ is already in the box: remove that old stone from its current position, then put the incoming stone at the back of the box.
2. The box has fewer than $$$m$$$ stones: put the incoming stone at the back.
3. The box is full and contains at least one broken stone: remove the first broken stone, then put the incoming stone at the back.
4. The box is full, all stones in it are unbroken, and $$$state_i=1$$$: remove the first stone, then put the incoming stone at the back.
5. The box is full, all stones in it are unbroken, and $$$state_i=0$$$: ignore the incoming stone.

The first stone is the one closest to the front of the box. The back is the opposite end.

There are also $$$k$$$ curse moments. Immediately after processing the $$$c_j$$$-th stone for every $$$j$$$, the curse reverses the whole current order of the box.

After all stones and curses are handled, output the final contents of the box from front to back.

You are given a set of $$$n$$$ red points and $$$m$$$ blue points in the Euclidean plane. No three points, ignoring their colors, are collinear.

A subset of at least three red points is called good if its points form a strictly convex polygon (i.e., every point in the subset is a vertex of its own convex hull).

Let $$$P$$$ be the convex polygon defined by a good subset. A good subset is valid if the interior of $$$P$$$ contains an odd number of blue points. Calculate the total number of valid good subsets, modulo $$$2$$$.

You are given an array $$$a$$$ of length $$$n$$$. You may color every position of the array either black or white. Let $$$D_B$$$ be the number of distinct values that appear in at least one black position, and let $$$D_W$$$ be the number of distinct values that appear in at least one white position.

Your task is to determine whether there exists a coloring such that $$$D_B = D_W$$$.