Ladies and gentlemen, David Blaine is back! Having realized that street magic is not as captivating to his audience as in the beginning of his career, David started having doubts about his capabilities. However after giving it another thought he understood that math magic is the new trend in the entertainment industry. We all know David does not bother about easy stuff and he loves stunning the crowd, so he decided to do a famous, but not yet performed by anyone trick with tens.
Here are the trick details. Two people from the audience pick an integer number each. Let's denote these numbers n and m. After that David calculates in his head the secret number x (it takes precisely 0.42 seconds). So what is so special about x? It is a positive integer number not greater n such that 
for any k > 0. David found out that there could be very many such numbers, so he wants to know exactly how many exist for given n and m.
Note: 
is modulo operation which finds the remainder after division of one number by another.
The first input line contains two positive integer numbers n and m which were picked by the audience.
The only output line should contain the number of possible secret numbers x modulo 109 + 7 for the given n and m.
72 4
42
Bernard saw a square box full of sweets and the variety of choices took him by surprise. The box has n × n cells and each cell has one candy of a specific type. The only thing perplexed Bernard is capable of at the moment is to randomly choose a rectangle of cells and eat all candies in them. However, Bernard never loses composure, so each rectangle has an equal chance to be chosen. We are just curious to know what is the expected number of different candies that are going to be eaten right now.
The first line contains an integer number n, where n is the size of the box. Following that are n lines each containing n integer numbers ai, j that denote types of candies in the box cells.
You got to know that all tests for this problem were generated randomly, i.e. for given n and k each cell of a box of size n × n contains one of k candy types, which was chosen randomly and uniformly.
Output the expected number of different types of candies that would be eaten by Bernard. Your output should have an absolute or relative error of at most 10 - 9.
3
1 2 3
2 2 3
3 1 1
1.8888888889
The society of crime fiction lovers holds meetings every day since September 13, 1842. Each day a member of the society with the membership card number x gives a talk. After more than 150 years the society chairmen collected enormous data about presenters, and it was decided to analyze it. Turns out, on the first society meeting a talk was given by the member number 1, on the second meeting spoke the member number 2, on the third day – 4, on the fourth day – 6, on the fifth day – 3 and so on. The chairman noticed, that each day the membership card number of the presenter is equal to the minimal positive integer number that is not coprime with the membership card number of the previous presenter and is not equal to membership numbers of those who gave talks before.
According to the tradition the card numbers of presenters were posted on the notice board, but in the Information Age the board was replaced with a digital screen. The society has bought software which computes the membership card number of the presenter on day n. However, the computation algorithm is very complex, so the society members is having doubts in its correctness. Could you please help them?
The only input line contains a single integer number n, which is the number of the day for which you need to determine the presenter.
Output the card number of the member who gives a talk on the n-th day.
35
42
Flash was born in the mid-1920s. Soon he will turn 100 years old, and according to the Justice League rules the superhero will have to resign and retire.
But even superheroes need to earn a living, so Flash has decided to register his brand to get paid for its licensing. Flash’s logo is an integral part of his brand. The logo looks like a polygonal chain on six vertices. When traversing the chain the segments turns alternate (first left turn, then right turn, then left, and so on) and the turns are sharp, i.e. greater than 
. Such polygonal chain looks like a flash.
The universe is represented by n points, each point represents a planet. According to the new law of the Interstellar Government every superhero can receive income of one space dollar per day if there are planets which could be connected with straight lines to represent the hero’s logo. Note that Flash could use planets multiple times to receive income from different logo configurations. Configurations are considered to be different if their planet order is different. Configurations that have reverse order are considered to be the same.
Flash has spent his whole life as a superhero, so he is not good at math. He would like to know how many space dollars would he earn per day if he registers his brand.
The first input line has a single positive integer number n, which is the number of planets in the universe. Following that are n lines each containing two integer numbers xi and yi, which represent coordinates of the i-th planet. The universe is finite and flat, but it is somewhat unique: no three planets are located along the same line.
The only output line should contain Flash’s daily income in space dollars.
6
0 3
-1 2
1 1
-2 0
1 -1
-1 -2
3
7
0 -5
-4 3
-5 8
4 0
-8 4
-1 1
2 5
42
The President of Bandiaterra Mr. Barbato is preparing for the next year upcoming elections. Nowadays his rating has fallen drastically to the lowest value ever (0.42%). The staff of president administration office have realized that they have to act in order for Mr. Barbato to save his office.
There are n citizens of Bandiaterra that are eligible to vote. Each of them is assigned to a particular electoral district. The electoral districts contain the same number of citizens each. The same principle is applied to split districts to subdistricts, subdistricts to subsubdistricts, subsubdistricts to subsubsubdistricts, etc. Splitting of an administrative unit (subdistrict) is allowed as long as the number of citizens in the unit is divisible by an integer.
Traditionally there are two candidates for the president office: the current president and an opposition candidate. Each citizen of the smallest administrative unit votes directly for a delegate, which is obliged to vote for the respective candidate at the next state of the election. Thus, after several stages of the election each elective district (the largest administrative unit) is represented by a delegate, and these delegates give their votes to candidates. According to the Bandiaterra constitution, if the candidates have equal number of votes, the opposition candidate wins.
Barbato was one of the election system's designers. For this reason, only the current president has the exclusive right to form the electoral districts. It means that Barbato is allowed to specify which citizens belong to which districts, as long as the numbers of the citizens in the districts respect the rules described above. Of course, Mr. President is going to hold a huge agitation campaign to convince the compatriots to vote for him. However, he would like to be sure that he will definitely be elected for a new term. Given that he decides on the structure of districts at all levels, what is the minimum number of votes that Barbato needs to guarantee his victory?
The first line contains a positive integer number n — the number of citizens that are eligible to vote in Bandiaterra.
Output a single line containing a single number — the minimum number of votes that would guarantee a victory for Barbato.
130
42
In Mexico far, far away, huge cactus plantations are spread all over the country. And also there live novice crooks Carlos and Pedro. Once they watched the film “The Godfather” and decided to become famous mafia bosses. But the serious arm ang drug dealers haven’t taken them to their gangs. So they decided to sell cactuses to the ardent foreign collectors.
When they arrived to the plantation, Carlos and Pedro found that it is impossible to carry away a huge thorny cactus in the hands. Then the unlucky bandits decided to cut it into pieces that are no more than two edges.
Calculate the possible number of different ways to cut a poor cactus. Print this big as Carlos and Pedro’s sorrow number modulo 109 + 7.
P.S. Cactus is a connected undirected graph in which every vertex belongs to no more than one simple cycle. In this problem vertex is the same as a thorn. Two ways are considered to be different if there is an edge between the thorns in one way and there is no edge between the same thorns in the other.
The first line of each test case contains two integer numbers n (the number of vertices) and m (the number of edges). The next m lines contain two integer numbers ui and vi (vertices connected by edges). It is guaranteed that there are no loops and multiple edges in the cactus graph.
Output the required number of cactus cuts modulo 109 + 7.
3 2
1 2
2 3
4
2 1
1 2
2
5 5
1 2
3 4
5 4
3 2
3 1
20
Being a teaching professor is a hard and thankless job. Throughout the semester students do not attend lectures because they prefer staying in their warm beds. If only they notified the staff they would be absent! But no, students always think it is only they who want to sleep… And in the end professors are forced to listen to their ridiculous answers during exams. The old professor is pretty tired of this iniquity, so he came up with a new way to give and grade exams.
There are n2 students in the group to which the professor gives exam. There are only two grades possible: "pass" and "fail". The professor has a square table of n2 cells; each cell represents the final grade of one of the students. Initially all cells contain "fail". The unaware prefect of the student group is asked to pick an arbitrary number k, and then the fun begins. The professor chooses an arbitrary row or column in the table and inverses all grades in it. He repeats this operation until exactly k students have "pass". At this point the exam is over, and the k lucky students go to celebrate the finals being over. However, there are cases when it is not possible for k students to pass the exam according to the professor’s scheme. In such cases everyone needs to retake the exam.
The best student have to help the prefect to find out if anyone would pass the exam if he picks number k.
The first input line contains two integer numbers n and t, where n is the size of the professor’s table and t is the number of tests. Second line contains four integer numbers q0 a b m. These numbers are used by the prefect to generate t numbers ki according to the following rule:
Output the number of numbers among ki (1 ≤ i ≤ t) for which it is possible for someone to pass the exam.
5 6
9 1 2 999999993
4
85 155
88 120 53 980090303
42
"We need to add a really simple task to the contest."
"A + B?"
"Yeah, sounds good."
"Will add in a moment."
...
"I've added it, but there is a problem."
"What?"
"I accidentally removed all the tests and only answers are left :("
"No worries, just upload them as tests."
"Um... What the task is about then?"
"Given the sum find a and b."
The first input line contains one integer number s.
Output two integer numbers a and b, such that a + b = s and |a|, |b| ≤ 1018. It is guaranteed that for the given s there is a solution within the limits. If several solution exist, output any.
43
42 1
Banking software is the most reliable software in the world. At least so claim its developers. But even it can fail, and a failure has happened at the "Horns and Hoofs” bank branch. All credit payments data is lost, and the bank is left with only debtors names database. It is a very objectionable situation. All debtors claim that their small debts were almost fully paid. And yet the SEO Plyushkin is having doubts, so he has decided that all debt amounts need to be recalculated. The debt amount is the difference between the credit amount and the already paid amount, which are represented as n-digit integer numbers (potentially with leading zeroes). The debt is calculated in the following way: the customer relations expert Durilkin picks a digit and the debtor Nakupilkin puts it in place of a digit in the not yet restored credit or payment amount number. This procedure is repeated until both numbers are restored. Durilkin wants to maximize the debt amount and Nakupilkin wants to minimize it.
You have a chance to act as both Durilkin and Nakupilkin, and you need to do it optimally. Of course, your opponent will play optimally.
The first input line contains two numbers t and n. t denotes the person which you are about to play for (1 for Durilkin, 2 for Nakupilkin). n denotes the number of digits in the credit and payment fields.
Durilkin picks a digit. If you act as him, you need to output it, otherwise you need to read it.
Then Nakupilkin picks the digit position and the field for the digit insertion. Nakupilkin names two numbers: r and c. If r is equal to one, he wants to edit the credit amount; if r is equal to two, then he wants to edit the payment amount. c denotes the digit index; the digit enumeration starts at the most significant digit. If you act as Nakupilkin, you need to output r c, otherwise you need to read these numbers.
Don’t forget to put a newline character and to flush the output stream after you print. For example, use fflush(stdout) in C++, System.out.flush() in Java, and flush(output) in Pascal.
In a country far far away there lived a King. That King had two sons. The first one, the younger one, loved math puzzles a lot, and his name was Alex Pop-o-witch. The older one, Ilya Murr-o-metz, wasn't fond of math. He was learning martial arts in order to be able to protect his motherland from enemies. Nevertheless, there were common activities for them to play together every day. Once the King decided to give a cherry orchard to his children as a gift. The orchard was in a form of a square with the opposite corners placed at the coordinates (0, 0) and (1, 1). All cherry trees were placed strictly inside the square. The sons were very happy with the gift because they now could not only run and play there, but also eat sweet cherries.
But soon the boys had a serious disagreement: Ilya didn't like the fact that Alex was doing math and had no interest in the martial arts, because the motherland was in danger and enemies may come at any moment. So the brothers were to split the cherry orchard. In this country far far away the older son always gets more than the younger one, and Ilya decided to take the part of the orchard that had more cherry trees to himself (he does not mind if both parts have the same amount). Alex didn't even object in order to avoid being lectured about enemies, fighting and battles. The boys selected two random points on the distinct sides of the orchard (each pair of points had the same probability to be picked) and connected both points using the rope thus splitting the orchard into two parts — one at each side of the rope. The section that had more cherry trees now belonged to Ilya, and the one with less — to Alex. You can consider that there is a zero a probability for the rope to cross the tree i.e. it is always possible to clearly distinguish to which part every tree belongs.
During the next year Ilya was eating cherries and doing sports. But soon Ilya got bored, because there were no cherries left and no one attacked the motherland. Meanwhile, Alex devoted himself to math. He is thinking about how many cherry tries he could have had if the brothers picked other random points during the orchard split. The only important condition is that Alex wouldn't have more trees than Ilya. He is curious to know what was the expected amount of cherry trees in his section of the orchard. Help Alex solve this tricky problem.
The first line consists of a single positive integer n — the number of cherry trees in the orchard. Following that are n lines, each line has two numbers xi and yi — coordinates of the trees with the precision not more than 3 digits after the floating point. All of the trees have distinct coordinates.
Output the single number: the expected amount of trees in the Alex's orchard section with the absolute and relative error no more than 10 - 9.
3
0.876 0.314
0.231 0.111
0.449 0.548
0.4200509661
2
0.001 0.998
0.999 0.002
0.6651766671