Humam (AKA Homam) goes fishing to put food on the table. One day, while using his fishing rod, he caught a bottle instead of a fish. Inside the bottle, he found a treasure map, and he was thrilled to discover the hidden treasure, leading him to stop fishing forever after.

He took his friend, Wael, saddled their horses, and went to the castle where the treasure was buried. They spent a week deciphering the riddles that led to the exact location of the treasure. Once they did, they started digging until they finally found the treasure, a buried array!

Both disappointed that the treasure was not money, gold or any valuable items, they started packing their things to head home. While doing so, Humam thought that he would take the array with him as a remembrance of this journey. Wael, not really caring about taking the array or leaving it, said: "Eh seedie, hot bel kherej". The kherej of Humam's horse was so small to fit the whole array, so he wanted to take a subset of its elements.

Humam thinks that a set of integer numbers is $$$\textit{good}$$$ if their product is divisible by $$$x$$$, where $$$x$$$ is Humam's lucky number.

Humam and Wael wanted to head home before it's dark. They want to find the minimum size of a subset of the buried array where it is $$$\textit{good}$$$. Can you help them?

a subset of an array $$$a$$$ is an array $$$b$$$ that can be obtained by removing zero or more elements from $$$a$$$.

"I added a problem, I deserve to be a judge", Radi said.

"You keep adding problems and work on them and over time, you will be a judge", the chief judge responded.

"No, I'm a judge", Radi insisted.

However, Radi added one problem and did no work on it, so he wasn't a judge.

The problem states that you are given two arrays $$$a$$$ and $$$b$$$ of $$$n$$$ integer numbers. You can do each of the following operations any number of times in any order:

• Choose an integer number $$$x$$$ and multiply all elements of $$$a$$$ by $$$x$$$.
• Choose an integer number $$$x$$$ and multiply all elements of $$$b$$$ by $$$x$$$.

You need to find the minimum number of operations needed so that $$$GCD(a_1, a_2 \dots a_n) = GCD(b_1, b_2 \dots b_n)$$$.

The greatest common divisor (GCD) of two or more integers is the largest positive integer that divides each of the integers.

KaitoKid knows every algorithm known to mankind. As he really enjoys learning new algorithms, he is now waiting desperately for a new algorithm to be created by the grandmasters of the world so that he can learn something new.

He once realized that he is a grandmaster himself, so he wanted to create a new algorithm. He came up with an algorithm called $$$k$$$-th LNCA.

In a tree, A node $$$u$$$ is considered the parent of a node $$$v$$$ if there is an edge between $$$u$$$ and $$$v$$$ and $$$u$$$ is closer to the root than $$$v$$$.

A node $$$u$$$ is considered an ancestor of node $$$v$$$ if $$$u$$$ is reachable from $$$v$$$ by repeated proceeding from $$$v$$$ to its parent.

A node $$$u$$$ is considered a common ancestor of a subset of $$$m$$$ nodes $$$v_1, v_2 \dots v_m$$$ is a node that is an ancestor of each of the $$$m$$$ nodes.

A node $$$u$$$ is considered the lowest common ancestor (LCA) of a subset of $$$m$$$ nodes $$$v_1, v_2 \dots v_m$$$ if $$$u$$$ is the lowest node (I.e. furthest from the root) that is a common ancestor of the subset.

As per KaitoKid, to check if a node $$$u$$$ is a $$$k$$$-th lowest not so common ancestor ($$$k$$$-th LNCA) of a subset $$$S$$$ of $$$m$$$ nodes $$$v_1, v_2 \dots v_m$$$, you do the following:

• Consider all of the subsets of $$$S$$$ that has exactly $$$k$$$ elements of $$$S$$$.
• Consider having a set $$$S_1$$$ that has all of the LCAs of each of the above described subsets.
• a node $$$u$$$ is a $$$k$$$-th LNCA if it is one of the lowest nodes (I.e. furthest from the root) in $$$S_1$$$.

After KaitoKid created this algorithm, he created a problem to train people on it. Given a tree of $$$n$$$ nodes rooted at $$$1$$$, you need to perform $$$q$$$ queries, in each query, you are given $$$k$$$, $$$m$$$ and a set of $$$m$$$ nodes $$$v_1, v_2 \dots v_m$$$, you need to find the number of nodes that are considered a $$$k$$$-th LNCA of the given set of nodes.

Yazan has two friends that he loves the most. He has got a new job offer, so he wanted to invite them for dinner at a fancy restaurant. As his salary is not so high, Yazan will invite his friends without ordering food for himself to save himself a few dollars.

Yazan will order one dish for each friend. The first friend will be happy if his dish costs at least $$$x$$$ dollars. The second friend will be happy if his dish costs at least $$$y\%$$$ of the total bill.

More formally, if Yazan ordered a dish that costs $$$a$$$ dollars for the first friend and a dish that costs $$$b$$$ dollars for the second friend, two conditions should be satisfied so that both of his friends are happy:

• $$$a$$$ and $$$b$$$ are integers.
• $$$a \ge x$$$.
• $$$b \ge \frac{y}{100}*(a+b)$$$.

Yazan wants both of his friends to be happy. Nevertheless, he also wants to spend as few dollars as possible, what is the minimum sum of costs of dishes he needs to order so that both friends are happy?

Bad Luck Blackie is a 1949 American animated comedy short film. They launched a new game recently where they give you an array $$$a$$$ of $$$n$$$ integer numbers, and an array $$$b$$$ of $$$n$$$ integer numbers. Initially, your score is zero.

In each second, you do the following operations in the same order:

• Choose an integer number $$$1 \le pos \le n$$$ as the Bad Luck Blackie.
• Add $$$a_{pos}$$$ to your score.
• Assign $$$a_{pos} := a_{pos} - b_{pos}$$$. Note that $$$a_{pos}$$$ can be negative after the assignment.
• For each $$$(1 \le i \le n, i \ne pos)$$$, assign $$$a_i := min(a_i + b_i, the\ initial\ value\ of\ a_i\ before\ doing\ any\ operations)$$$.

Your task is to find the maximum score you can get after $$$k$$$ seconds. Can you win the game?

Anas was thinking about getting his friend and teammate, Majed, a present for his birthday. And who's better at suggesting good birthday presents than codeforces suggesting an array?

Anas decided to gift Majed an array $$$a$$$ of $$$n$$$ integer numbers as codeforces suggested. The cost of a subarray $$$a_l, a_{l+1} \dots a_r$$$ is the sum of its elements modulo $$$m$$$. More formally, the cost of the subarray of $$$a$$$ is $$$(a_l + a_{l+1} + \dots a_r)\ mod\ m$$$.

Majed wrote the cost of all $$$\frac{n \times (n+1)}{2}$$$ subarrays on a whiteboard. He then summed the largest $$$k$$$ numbers on the whiteboard. Can you find that sum?

An array $$$b$$$ is a subarray of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

Naseem has $$$n$$$ children. Instead of giving each child his own name, he gave each child $$$i$$$ a number $$$a_i$$$. Note that there might be two children with the same number. More formally, for $$$i$$$ and $$$j$$$ where $$$i \ne j$$$, $$$a_i$$$ can be equal to $$$a_j$$$

Sometimes, Naseem gets back home and sees that some children went to enjoy their life (like going to the playground, solve some codeforces problems etc..), so he gets worried and start to check the smallest non-negative integer $$$x$$$ such that there is no child with number $$$x$$$ currently at home (which is called the MEX). and goes looking for children with their number equal to this MEX.

This process is tiring for him, especially that his eyes does not function that good. He asked you to write a program that is given $$$n$$$ and an array $$$a$$$ of length $$$n$$$, it finds the sum of MEX of every subsequence of $$$a$$$.

A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements

The MEX (minimum excluded) of a set is the smallest non-negative integer that does not belong to the set.

The judges were overwhelmed by how much work they need to put on the contest, especially that most of them either have jobs, exams or both. They were trying hard to come up with problem ideas and then work on them.

Obada, this problem's author, told the judges he had a cool problem idea and he'll add it soon. A few days before the contest, he finally added the problem.

For a permutation $$$p$$$ of length $$$n$$$. You can do the following operation any number of times:

• Choose two integer numbers $$$l$$$ and $$$r$$$ $$$(1 \le l_i \lt r_i \le n)$$$, where $$$l$$$ should be greater than $$$l$$$ chosen in the previous operation. More formally, in the $$$i-th$$$ operation where $$$i \gt 1$$$, $$$l_i$$$ > $$$l_{i-1}$$$.
• Reverse the subarray $$$a_l, a_{l+1}, \dots a_r$$$.

The cost of a permutation $$$p$$$ is the minimum number of operations you need to do so that $$$p$$$ is sorted in ascending order.

Given an integer number $$$n$$$, find the sum of costs over all permutations of length $$$n$$$ modulo $$$10^9 + 7$$$.

Antwan is a scout in the army at the frontline. He wants to get through the enemy's camp.

To reach the camp, Antwan needs to cross a cornfield of $$$n+2$$$ sectors numbered from $$$0$$$ to $$$n+1$$$. The enemy knew beforehand that some scouts might cross the field, so they planted $$$m$$$ self-detonating land mines, each land mine $$$i$$$ where $$$1 \le i \le m$$$ is placed at sector $$$a_i$$$ where $$$1 \le a_i \le n$$$ and will detonate after $$$b_i$$$ hours, killing every scout in sector $$$a_i$$$. Note that both sectors $$$0$$$ and $$$n+1$$$ does not have any land mines.

Antwan is currently at sector $$$0$$$ of the cornfield and the enemy's base is at sector $$$n+1$$$. He wants to cross the cornfield as fast as possible.

Antwan can go from sector $$$x$$$ to sector $$$x+1$$$ in one hour. Once he starts crossing the field, he can make $$$\textbf{at most one}$$$ stop at any sector he chooses (possibly at sector $$$0$$$) for as many hours as he wants, then he will continue crossing the cornfield. More formally, If Antwan wants to stop at sector $$$x$$$ for $$$y$$$ hours where $$$0 \le x \le n$$$ and $$$y \ge 0$$$, at hour $$$0$$$ he will be at sector $$$0$$$, at hour $$$1$$$ he will be at sector $$$1$$$ and so on, at hours $$$x, x+1 \dots x+y$$$ he will be at sector $$$x$$$, at hour $$$x+y+1$$$ he will be at sector $$$x+1$$$ and so on until he reaches sector $$$n+1$$$ where the enemy's camp lies.

Of course, Antwan does not want to be blown by a land mine. Nevertheless, he wants to reach the camp as soon as possible. What is the minimum time Antwan needs to reach the enemy's camp?

Mohannad's hobby involves inventing pointless machines for enjoyment. Today, he invented the set terminator machine.

Before he starts the set terminator, Mohannad chooses three integer numbers $$$m$$$, $$$k$$$ and $$$q$$$ as a preset. Mohannad would then provide the set terminator with a set $$$s$$$ of $$$n$$$ integer numbers (not necessarily distinct), all between $$$1$$$ and $$$m$$$.

Once Mohannad turns on the set terminator, it will generate an array $$$a$$$ of $$$q$$$ integer numbers, where $$$1 \le a_i \le m$$$. The set terminator would then do $$$q$$$ operations, in the $$$i$$$-th operation, it will do the following:

• The set terminator will add $$$a_i$$$ to the set.
• The set terminator will then terminate (I.e. remove) the $$$k$$$-th smallest integer number in the set. For example, if the set contains the integer numbers $$$\{1, 2, 2, 4\}$$$ and $$$k=3$$$, the set terminator will remove a $$$2$$$ and the set will be $$$\{1, 2, 4\}$$$.

After the set terminator is done working, it will print the sum of all of the integer numbers of the set on its screen.

As Mohannad does not really know what are the values of the array $$$a$$$, he is interested in finding the sum of answers printed on the screen of the set terminator in all of the $$$m^q$$$ ways to generate the array $$$a$$$. As this might take forever, can you help Mohannad?

Noclipping is a temporal phasing that allows one to bypass the normal boundaries of spatial reality. Urban legends suggest that once you noclip out of reality, you'll end up in the backrooms.

Unfortunately for Moussa, he wasn't careful and he noclipped into the backrooms. Luckily, he read the online threads and watched the footages. He knows that the backrooms consists of $$$n$$$ rooms numbered from $$$1$$$ to $$$n$$$, there are $$$m$$$ passages where the $$$i$$$-th passage links the rooms $$$a_i$$$ and $$$b_i$$$. In simpler words, the backrooms are a connected undirected graph.

Moussa is currently at room $$$1$$$ and he needs to reach room $$$n$$$. He can go through any passage in $$$1$$$ second. As all of the backrooms look the same, Moussa's approach is whenever he is in room $$$u$$$, he will use any passage to go to any other room. The passage is chosen randomly. More formally, if Moussa is currently at room $$$u$$$ that has $$$x$$$ passages, he will use a random passage with probability $$$\frac{1}{x}$$$ to go to another room and so on until he reaches room $$$n$$$.

Moussa knows that each room from $$$2$$$ to $$$n-1$$$ has exactly one monster. Once Moussa enters a room $$$i$$$ that has a monster, the monster have probability $$$p_i$$$ to be asleep and probability $$$1-p_i$$$ to be awake. If the monster is asleep, Moussa will leave the room peacefully. If the monster is awaken, Moussa is in no danger because as a minecraft expert, he knows how to craft a potion using no material and kill the monster in $$$2$$$ seconds, then he can leave the room to another room. Once a monster is killed, he will be dead until the end of the journey.

Moussa is already terrified being in the backrooms. He wants to find the expected number of seconds he will need to leave the backrooms so he can continue working on the problems you are solving right now. He cannot waste any time finding the value, so can you find it instead?

Naseem washes his socks in the washing machine. He always put all of his socks in the washing machine, then once the washing machine is done, he sits and pairs them before putting them in the closet.

Naseem is in a rush today, so he wanted to know how many pairs he has before leaving his apartment. Naseem has $$$n$$$ socks, what is the maximum number of pairs of socks do they make?

The company of gums and lollipops has exactly $$$k$$$ types of employees numbered from $$$0$$$ to $$$k-1$$$. The employees of the company are split into $$$n$$$ squads. The $$$i$$$-th squad is represented as an integer number $$$a_i$$$ where the squad has an employee of the $$$j$$$-th type iff the $$$j$$$-th bit in the binary representation of $$$a_i$$$ equals $$$1$$$.

The efficiency of the $$$i$$$-th type of employees equals $$$2^i$$$ iff each of the $$$n$$$ squads has an employee of the $$$i$$$-th type. Otherwise, it's $$$0$$$.

The efficiency of the company of gums and lollipops is the sum of efficiencies of all of the employee types the company has.

Philip is the manager of the company. Everyone thinks that he is not a good manager because of his profile picture, so he wanted to prove them wrong and do some changes that would increase the efficiency of the company.

For each $$$i$$$ from $$$1$$$ to $$$n$$$, he will choose $$$\textbf{exactly}$$$ one of the following operations and perform it on the squad $$$\textbf{exactly}$$$ once:

• Fire an employee from the squad to cut costs.
• If the squad has no employee of the $$$j$$$-th type, hire an employee of the $$$j$$$-th type and assign him to the $$$i$$$-th squad.

He wants to do the operations so that the efficiency of the company is maximized. He is really a kid who does not know what he is doing, so he assigned this task to you as the assistant manager of the company of gums and lollipops. Go on and prove them wrong so that Philip is not a kid in people's opinion.