In the whimsical land of Sweetonia, there live two tiny candy dragons: Choco and Caramel. Every morning, they collect candies from the Candy Forest.

Choco finds $$$a$$$ candies.

Caramel finds $$$b$$$ candies.

They want to put all their candies together in a magical jar to share with the village kids.

Your task is to help them find out how many candies they have in total.

Alice and Bob want to play a game on a rectangular grid. They consider the game fair if the grid on which the game is played is a square (i.e., has equal side lengths).

However, they currently have an $$$n \times m$$$ grid (where $$$n$$$ is not necessarily equal to $$$m$$$). They decided to take multiple copies of this $$$n \times m$$$ grid. These copies must maintain their original $$$n \times m$$$ orientation (no rotation allowed) and must be attached together side-by-side, without intersections, to form a perfect square grid.

They are asking you to determine the minimum number of $$$n \times m$$$ grid copies required to achieve this. Can you help them?

You have a parking lot of $$$n$$$ parking spots and a queue of cars with $$$n$$$ cars numbered from $$$1$$$ to $$$n$$$, where the first car in the queue is $$$1$$$ and the last is $$$n$$$ (i.e. they are sorted in increasing order).

In this parking lot, there are parking spots reserved for specific cars, so for the $$$i$$$-$$$th$$$ parking spot if $$$a_i=0$$$ then there are no reservations for this spot and anyone can park here, else if ($$$1 \le a_i \le n$$$) then this spot is reserved for the $$$a_i$$$-$$$th$$$ car only and no other car can park here, note that it is reserved for $$$a_i$$$-$$$th$$$ car but that car doesn't necessarily have to park here.

Cars come to the parking lot one by one starting from the $$$1$$$-$$$st$$$ car and finishing with the $$$n$$$-$$$th$$$ car and each car has to park in one of the $$$n$$$ parking spots. Each parking spot should have exactly one car.

Unfortunately, all $$$n$$$ cars drivers are girls, and as you know, girls are not good at driving, so a car $$$j$$$ cannot park in the $$$i$$$-$$$th$$$ parking spot if ($$$2 \le i \le n-1$$$) and there are cars that already parked in spots $$$i-1$$$ and $$$i+1$$$, otherwise car $$$j$$$ can park safely.

For example, if $$$a = [0,1,0,0,0]$$$ then possible valid arrangements for cars are $$$[2,1,3,4,5]$$$ and $$$[3,1,2,4,5]$$$, while $$$[5,4,3,2,1]$$$ is not valid because the $$$2$$$-$$$nd$$$ spot is reserved for car $$$1$$$ while car $$$4$$$ parked there, and $$$[3,1,4,2,5]$$$ is not valid because car $$$4$$$ parked in $$$3$$$-$$$rd$$$ spot while $$$2$$$-$$$nd$$$ and $$$4$$$-$$$th$$$ spot where already filled.

Since you are obsessed with the number of possible arrangements of anything, you are interested in knowing how many ways are there possible to arrange the cars in the parking lot.

Since the answer can be very large, print it modulo $$$10^9+7$$$.

You are given a permutation $$$p_1, p_2, \dots, p_n$$$ of length $$$n$$$. The elements of $$$p$$$ are a permutation of the integers $$$0, 1, \dots, n-1$$$.

For a non-empty array $$$a = [a_1, a_2, \dots, a_m]$$$, we define the function $$$f(a)$$$ as: $$$$$$ f(a) = (a_1 | a_2 | \dots | a_m) \times \text{MEX}(\{a_1, a_2, \dots, a_m\}) $$$$$$

Your task is to calculate the sum of $$$f$$$ applied to all contiguous subarrays of $$$p$$$. You need to compute the value $$$S$$$, modulo $$$10^9 + 7$$$: $$$$$$ S = \sum_{l=1}^n \sum_{r=l}^n f([p_l, p_{l+1}, \dots, p_r]) $$$$$$

Here, $$$(a_1 | a_2 | \dots | a_m)$$$ represents the result of applying the bitwise-OR operation to all elements $$$a_1, a_2, \dots, a_m$$$. For example, if $$$a = [1, 2, 4]$$$, the bitwise OR is $$$1 | 2 | 4 = 7$$$.

The function $$$\textbf{MEX}(S)$$$ for a set of non-negative integers $$$S$$$ is defined as the smallest non-negative integer that is not present in the set $$$S$$$. For example, $$$\text{MEX}(\{0, 1, 3\}) = 2$$$ and $$$\text{MEX}(\{1, 2\}) = 0$$$.

Naseem is working on "The Line", a project involving $$$n$$$ buildings arranged in a sequence. The design for each building is represented by a character in a string $$$s = s_1s_2\dots s_n$$$ of length $$$n$$$, using lowercase Latin letters ('a'-'z').

Naseem defines the beauty of "The Line" based on its string representation $$$s$$$. The beauty is the length of the longest prefix of $$$s$$$ consisting of only one distinct character. Formally, it's the largest integer $$$x \le n$$$ such that all characters $$$s_1, s_2, \dots, s_x$$$ are identical. (For example, the beauty of "aaabbc" is $$$3$$$, the beauty of "b" is $$$1$$$).

To potentially improve the beauty, Naseem can perform the following operation at most once: choose a (possibly empty) contiguous substring $$$s[l..r]$$$ ($$$1 \le l \le r \le n$$$) and delete it. The remaining parts of the string (if any) are concatenated together in their original order.

Your task is to help Naseem find the maximum possible beauty achievable for "The Line" after performing the operation at most once.

Kinan wanted to attend the World Cup so badly, but sadly he did not have enough money to make it there, so he went robbing banks around the city with the help of his friend Rajaee.

One day while they were doing their job in some bank, they found a precious array $$$a_1, a_2, \dots, a_n$$$ of positive integer numbers and each one of them wanted to take that array for himself.

They came up with the idea of splitting the array elements into exactly two groups, one for Kinan(group $$$1$$$) and one for Rajaee(group $$$2$$$), according to some conditions to guarantee justice. The conditions are described in the following:

• Each element should belong to exactly one group.
• One of the two groups can be empty.
• Every pair of elements belonging to the same group must be coprime.

Two positive integers $$$x, y$$$ are coprime if their greatest common divisor is $$$1$$$, $$$\gcd(x,y) = 1$$$.

You are asked to predict a way Kinan and Rajaee can split the array according to these rules, or state that they cannot split it. If there are many ways to split the array, printing any valid way is acceptable.

Duckduck is a marathon runner who has qualified for the 2024 Olympics in Paris.

The Olympic Games will start in $$$n$$$ days, and Duckduck needs to practice for his race, so he has decided to train every day from day $$$1$$$ to day $$$n$$$ until the Olympics begin. Each day, Duckduck runs $$$k$$$ kilometers, where the distance $$$k$$$ is chosen randomly and independently from the set $$$\{0, 1, \dots, 12\}$$$. For each $$$k$$$ from $$$0$$$ to $$$12$$$, the probability of running exactly $$$k$$$ kilometers on a single day is given as $$$\frac{p_k}{100}$$$.

As you might expect from his name, Duckduck is not very smart. Duckduck believes he will win the gold medal if the total distance he runs over the $$$n$$$ days is exactly $$$x$$$ kilometers.

Your task is to calculate the probability that the total distance run after $$$n$$$ days is exactly $$$x$$$.

The probability can be expressed as an irreducible fraction $$$\frac{P}{Q}$$$. Since the answer might be large, you should calculate and print the value $$$P \cdot Q^{-1} \pmod{10^9 + 7}$$$, where $$$Q^{-1}$$$ is the modular multiplicative inverse of $$$Q$$$ modulo $$$10^9 + 7$$$.

Given an array $$$a$$$ of length $$$n$$$ $$$(1 \le n \le 2 * 10^5)$$$ its elements are numbered from 0 to $$$n - 1$$$ $$$(a_0,a_1,...,a_{n-1})$$$.

For two integers $$$start$$$ and $$$step$$$ $$$(0 \le start,step \le n-1)$$$ define $$$f(start,step)$$$ as follows:

first set an integer $$$current$$$ to $$$start$$$ and set another integer $$$sum$$$ to zero, that is $$$current = start$$$ and $$$sum = 0$$$.Then repeat this steps $$$n$$$ times:

1. add $$$a_{current}$$$ to $$$sum$$$, that is $$$sum = sum + a_{current}$$$.
2. set $$$a_{current}$$$ to zero, that is $$$a_{current} = 0$$$.
3. add $$$step$$$ to $$$current$$$ modulo $$$n$$$, that is $$$current = (current + step)$$$ $$$mod$$$ $$$n$$$

If We Choose $$$start$$$ and $$$step$$$ randomly, what is the expected value of the function $$$f(start,step)$$$ modulo $$$10^9 + 7$$$.

Let $$$p_1, p_2, \dots, p_n$$$ be a permutation of the integers $$$\{1, 2, \dots, n\}$$$.

Define the prefix maximum array $$$b_1, b_2, \dots, b_n$$$ for the permutation $$$p$$$ as follows: $$$$$$ b_i = \max(p_1, p_2, \dots, p_i) \quad \text{for } (1 \le i \le n) $$$$$$

The permutation $$$p$$$ is called good if its prefix maximum array $$$b$$$ satisfies the following condition: $$$$$$ b_i - b_{i-1} \le 1 \quad \text{for all } i \text{ such that } (2 \le i \le n) $$$$$$

Given an integer $$$n$$$, your task is to count the number of good permutations of size $$$n$$$. Since the count can be large, output the result modulo $$$10^9 + 7$$$.

You are given an array $$$a_1, a_2, \dots, a_n$$$ of length $$$n$$$. The elements $$$a_i$$$ are distinct positive integers.

Your task is to compute the following sum: $$$$$$ S = \sum_{i=1}^n \sum_{j=i+1}^n \text{MSB}(a_i \oplus a_j) $$$$$$

The operator $$$\oplus$$$ denotes the bitwise-XOR operation.

The function $$$\textbf{MSB}(x)$$$ for a positive integer $$$x$$$ denotes the index (power) of the most significant bit in the binary representation of $$$x$$$.

This is equivalent to finding the largest integer $$$k$$$ such that $$$2^k \le x$$$. The value returned is $$$k$$$.

The binary representation of $$$20$$$ is $$$10100_2$$$. The most significant bit is $$$2^4$$$. Thus, $$$\text{MSB}(20) = 4$$$, $$$\text{MSB}(13) = 3$$$, and $$$\text{MSB}(8) = 3$$$.

You are given a tree of $$$N$$$ vertices rooted at vertex $$$1$$$ and a permutation $$$p$$$ of length $$$N$$$. For an array $$$\mathbf{a}$$$ of length $$$M$$$, we define the function $$$f(a)$$$ as the smallest size of a subgraph of the given tree that contains all the vertices $$$a_1, a_2, \dots, a_M$$$. We define $$$\text{dist}(u, v)$$$ as the number of edges on the path between vertices $$$u$$$ and $$$v$$$.

You have to answer $$$Q$$$ queries online, each query is of the following type:

• $$$v$$$ $$$k$$$ : Let $$$S$$$ be the set of vertices $$$u$$$ such that $$$\text{dist}(1, u) = k$$$, and $$$v$$$ is an ancestor of $$$u$$$. Then we define the set $$$H$$$ as the set of vertices $$$p_u$$$ for all $$$u \in S$$$.

The answer to the query is $$$f(H)$$$.

Note the unusual input format.

Jaber has a tree in his garden, the tree has $$$n$$$ nodes and $$$n$$$-1 edges. Sadly the tree nodes are colored blue. Jaber hates every blue cell on earth, so he will try to color it red, but he needs your help to answer these questions.

He will give you the structure of the tree , and $$$q$$$ queries of two types:

• 1 $$$u$$$ color the node $$$u$$$ in red.
• 2 $$$u$$$ $$$v$$$ find the maximum value of $$$F(P(u,v),P(i,j))$$$ where $$$i$$$, $$$j$$$ are red nodes, if there are less than two red nodes print 0.

$$$F(S_1,S_2)$$$ is the size of the intersection of two sets $$$S_1$$$, $$$S_2$$$.