There is a chessboard containing $$$n$$$ rows and $$$m$$$ columns. Cell at the $$$i^{th}$$$ row and $$$j^{th}$$$ column is denoted as $$$(i,j)$$$. Cell $$$(i,j)$$$ is colored white if $$$(i+j)$$$ is even; otherwise, it is colored black.

Your task is to place the maximum kings on white cells such that no two kings attack each other.

Two kings will attack each other if their cells are adjacent by edge or corner.

Zogbi is playing a video game, in which there is a circle divided into $$$n$$$ equal sectors, and initially each sector has a cone in it. She wins the game if she moves all the cones to any one specific sector in the minimum number of operations.

In one operation, she can select any two distinct cones and must move both of them independently to any one of their adjacent sectors from their current sector.

Note: two sectors are adjacent if they share a side in circular order.

For example, consider the case $$$n = 4$$$, as shown below. In each operation, she moves the two cones shown by red arrows to an adjacent sector. She makes exactly two operations to move all cones to one same sector. And it can be shown that one cannot do it in less than $$$2$$$ operations.

n = 4, operations are shown by red arrows.

Find the minimum number of operations. If it is impossible to move all cones to the same sector, output $$$-1$$$ instead.

You will be given a tree containing $$$n$$$ nodes. An unordered pair $$$(u,v)$$$ is called a Super Pair if it satisfies the following conditions:

1. $$$u≠v$$$;
2. Initially, there will be no edge between node $$$u$$$ and node $$$v$$$;
3. If we add an edge between $$$u$$$ and $$$v$$$, there will be exactly one shortest path between every pair of nodes. Note that we don't add this edge in the tree actually.

Your task is to calculate the number of Super Pairs.

Pritesh had a permutation $$$p$$$ of length $$$n$$$. He took all the prefixes $$$[p_1, p_2, \dots, p_i]$$$ ($$$1\leq i\leq n$$$) of the permutation $$$p$$$ and calculated the $$$\operatorname{MEX}$$$ (minimal excluded element) of each prefix. Unfortunately, he forgot the permutation but remembers the sum $$$S$$$ of all the MEX values. Can you help him find the permutation $$$p$$$?

If there are multiple solutions, print any of them. If there is no solution, print a single integer $$$-1$$$.

The $$$\operatorname{MEX}$$$ of a collection of integers $$$c_1, c_2, \ldots, c_k$$$ is defined as the smallest non-negative integer $$$x$$$ which does not occur in the collection $$$c$$$.

A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$0$$$ to $$$n-1$$$ in arbitrary order. For example, $$$[2, 3, 1, 0, 4]$$$ is a permutation, but $$$[0, 1, 1]$$$ is not a permutation ($$$1$$$ appears twice in the array), and $$$[0, 2, 3]$$$ is also not a permutation ($$$n = 3$$$ but there is $$$3$$$ in the array).

You have $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ written from left to right. For all integers $$$1 \leq i \lt n$$$, you can either put an XOR symbol ($$$\oplus$$$) or an ADD symbol ($$$+$$$) between $$$a_i$$$ and $$$a_{i+1}$$$ to form an expression. The cost of the expression formed is the alternative result of the expression itself. Find the sum of costs from all possible $$$2^{n-1}$$$ expressions. Since the sum of costs might be too large, find the sum modulo $$$998244353$$$.

The alternative result of an expression is the result of the expression if the XOR operation is done before any other operation. For example, the alternative result of $$$5 + 3 \oplus 5$$$ is $$$5 + 6 = 11$$$ since $$$3 \oplus 5 = 6$$$ and the XOR operation has to be done before the ADD operation.

This time Yugandhar came up with two binary strings $$$a$$$ and $$$b$$$ of length $$$n$$$ and is thinking of asking you to construct a binary matrix which has $$$n$$$ rows and $$$n$$$ columns, such that the following condition holds:

1. Bitwise AND of all the numbers in the $$$i^{th}$$$ row of the constructed matrix will be equal to $$$a_{i}$$$ $$$(1 \le i \le n)$$$.
2. Bitwise OR of all the numbers in the $$$i^{th}$$$ column of the constructed matrix will be equal to $$$b_{i}$$$ $$$(1 \le i \le n)$$$.

But Wuhudsm thinks it is boring to concentrate on a single thing. Hence, he asked you to calculate the number of different binary matrices of size $$$n$$$ rows and $$$n$$$ columns which you can construct to make the above conditions hold.

The number may be large so print it modulo $$$10^{9}+7$$$.

Alice and Bob play a game on two positive integers $$$x$$$ and $$$y$$$. They take turns alternatively, with Alice making the first move. In a move, a player can subtract a multiple of one number from the other number. After the operation, both should remain non-negative. The first person to make the value of $$$x \cdot y$$$ equal to $$$0$$$ wins.

An example of the game on $$$x = 4$$$, $$$y = 14$$$:

• Alice subtracts $$$8$$$ (a multiple of $$$x=4$$$) from $$$y = 14$$$. Now, $$$x = 4$$$ and $$$y = 6$$$;
• Bob subtracts $$$4$$$ (a multiple of $$$x=4$$$) from $$$y = 6$$$. Now, $$$x = 4$$$ and $$$y = 2$$$;
• Alice subtracts $$$4$$$ (a multiple of $$$y=2$$$) from $$$x = 4$$$. Now, $$$x = 0$$$ and $$$y = 2$$$. After that, Alice wins since $$$x \cdot y = 0$$$.

Given two positive integers $$$l$$$ and $$$r\ (l \le r)$$$. Your task is to find the number of ordered pairs $$$(x,y)$$$ such that $$$l \le x \le y \le r$$$ and Alice wins for these pairs.