Pheatr has a lot of accounts competing in online programming contests such as contests on TopForces.

Sometimes when Pheatr participates in a contest on TopForces but cannot attain a good score directly, he takes advantage of some extra accounts applied for cheating (i. e. sockpuppets) to achieve a higher score: Initially, he builds some wrong codes which can pass the pre-system tests and submits them through the sockpuppets. After that, he uses his main account to challenge these sockpuppets immediately, since a successful challenge provides him $$$100$$$ more score points.

Actually, Pheatr is not the only one who cheats in the contests. Many competitors use the same strategy during online programming contests. It is well known that everyone has only one account as the main account. If one's cheating is revealed, the main account of the one will be banned forever. To prevent the notorious fact from being exposed, each competitor would not register more than two sockpuppets. In spite of great peril, when they register their sockpuppets, these competitors always follow the same rule that the username of a sockpuppet belonging to one competitor should be a prefix of that of the competitor's main account, otherwise the username of the main account should be a prefix of that of the sockpuppet.

Recently, a leak from TopForces provided a list of verified cheaters who have used sockpuppets for cheating, containing the usernames of their main accounts. Besides, TopForces also published a list of suspicious accounts, implying some of them may be sockpuppets. In order to differentiate these suspicious accounts and point out their owners, Pheatr intends to describe all the possibilities according to the published information. Certainly, one should notice that some of the suspicious accounts may be wronged and do not belong to any known cheaters.

After recognizing your outstanding programming skills, Pheatr asks you to count the number of distinct possibilities in total for claiming the affiliations between verified cheaters and suspicious accounts. Two possibilities are considered the same if each suspicious account is wronged simultaneously or belongs to the same competitor in both possibilities. Since the answer can be pretty large, you are only asked to report the answer modulo $$$(10^9 + 7)$$$.

The RBM Second Generation of Dual Core Microprocessor Chip, also known as RBM2gDCMC, can generate a digital sequence of length $$$n$$$. Each digit in a sequence provided by RBM2gDCMC is regarded as an integer between $$$1$$$ and $$$n$$$ in this problem.

Now I will show you the passcode for the email belonging to Gini Romety, which is a sequence of length $$$m$$$ with integers between $$$1$$$ and $$$n$$$. You are asked to calculate the probabilities of the coincidence with Gini Romety's passcode for all consecutive subsequence of length $$$m$$$ in a sequence generated by RBM2gDCMC.

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at an iteration.

More precisely, insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

This type of sorting is typically done in-place, by iterating up the array, growing the sorted array behind it. At each array-position, it checks the value there against the largest value in the sorted array (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted array, shifts all the larger values up to make a space, and inserts into that correct position.

The resulting array after $$$k$$$ iterations has the property where the first $$$k$$$ entries are sorted. In each iteration the first remaining entry of the input is removed, and inserted into the result at the correct position, thus extending the result.

Knuth is an ACM-ICPC master and provides a modified pseudocode implementation about the insertion sort for you. His modified algorithm for an array of sortable items $$$A$$$ ($$$1$$$-based array) can be expressed as:

He notes that a permutation of $$$1$$$ to $$$n$$$ is almost sorted if the length of its longest increasing subsequence is at least $$$(n - 1)$$$.

Given the parameter $$$k$$$, you are asked to count the number of distinct permutations of $$$1$$$ to $$$n$$$ meeting the condition that, after his modified insertion sort, each permutation would become an almost sorted permutation.

Given a weighted tree $$$T_0$$$, we define its diameter as the length of the longest path between two vertices on it, where the length of a path is equal to the sum of weights of edges in the path.

If the tree stretches like a spider or a yawning tiger, its diameter will change. Let's use $$$T_i$$$ to denote the state of the tree after $$$i$$$ seconds, at which time the weight of each edge has been increased by exactly $$$i$$$ units from $$$T_0$$$.

You will be presented with several different queries, and you should calculate the tree's diameter at some specified time for each query.

The story centres around $$$n$$$ rival ninja clans labelled from $$$1$$$ to $$$n$$$, and $$$n$$$ ninjas also labelled from $$$1$$$ to $$$n$$$. For each ninja, the family decides his/her initial belief and affiliation of a clan. But some conflicts occur in the story, such as two young souls, facing the rivalry between their ninjas but falling in love, can change their mind and some ninjas may desert to other opposite clans.

These ninjas are living in a pretty quiet town with straightforward footpaths, but they live like a group of wild animals eyeing up ninjas of other clans, continually escaping and looking forward to killing. The governor of this region knows that the end of the war between them depends on those ninjas belonging to different clans who have the farthest distance.

That is what a noble vulture as the honest servant of the governor should do. Now you need to act as a vulture, and report in real time to the governor the largest distance between two ninjas that belong to different clans and whose labels are in a specified consecutive range. As a practical matter, the distance between two points in the plane is defined as the Manhattan distance, which is equal to the sum of the absolute differences of their Cartesian coordinates.

Ami Dongsuo, the god of the hills in Tibetan, guards the Qilian Mountains, whose Chinese name is Niuxin Mountain. Ami Dongsuo is a holy mountain which is famous for the fantastic love story about Zhuoer Mountain. The surrounding environments prompt Ami Dongsuo to form a huge sheep farmland.

According to a shocking new report by the excellent ecologist Mr. Ma, Ami Dongsuo has $$$n$$$ different pastures in total. With the help of local herdsmen, Mr. Ma describes the number of sheep in each pasture and all paths between different pastures.

Today, under his leadership, three adventurers Alice, Bob and Carol decide to visit some pastures in Ami Dongsuo. Mr. Ma has shown them a requirement, which is described by an integer $$$k$$$ that they should meet. These three adventurers will start their tours at the same pasture and visit three different routes, where their starting point is selected by themselves and thus it could be anywhere. Furthermore, a route may pass through one or more pastures. Since the altitude rises to nearly $$$5000$$$ meters at the peak, and going up the hill or even climbing is quite a tiring job, adventurers have reached an agreement that the altitudes at all pastures in a route should be strictly decreasing in visiting order. If go along their routes respectively, they will finally arrive at some pastures, which may not be distinct. The requirement described by $$$k$$$ from Mr. Ma requires that the total number of sheep in these three destinations, considering with the multiplicities, is equal to $$$k$$$.

Now, Mr. Ma hopes that someone can tell him, for any positive integer $$$k$$$, how many different plans exist for Alice, Bob and Carol that would meet what he requires. In this problem, we consider a plan as a set with three different routes sharing the common starting point. Two routes are considered different if their starting points vary or their sequences of visited paths in order vary. Two plans are considered different if at least one route that is contained in one plan but not in the other exists.

One day an excellent ACMer will leave the field to face new challenges, just like what the predecessors are doing. Some of them have taken over their family businesses, and some of them are struggling with the edges of unemployment. Some of them have the courage to display themselves and become a professional Ingress player, and some of them are still pushing themselves to limits and try to solve all problems in Project Euler.

But all these destinations are so shallow for Benecol de Cecco, the former king. What he does now is to be the best respondents in StackOverflow. StackOverflow is the largest, most trusted online community for developers to learn, share their programming knowledge, and build their careers.

Today, he notices a question which is posted by Kevin Li, saying: Recently, I implemented an experiment where I need to find all the data records whose Euclidean distances to the query point $$$q$$$ are the same value $$$r$$$. I tried to use the k-d tree to improve the search efficiency. However, I found that the k-d tree needs to traverse all leaf nodes to return the result, that is, it still needs to compare all dataset to obtain the result.

This question can be formalized to build a database with real-time queries and modifications. In the beginning, suppose we have $$$n$$$ different points in the plane. The $$$i$$$-th point is located at $$$(x_i, y_i)$$$ and has a weight $$$w_i$$$. Then we consider several queries and modifications dynamically given by

• 1 x y w, to insert a new point at $$$(x, y)$$$ of weight $$$w$$$, where we guarantee that before the operation no point was located in the place;
• 2 x y, to delete the point located at $$$(x, y)$$$, where we guarantee that the point existed before the operation;
• 3 x y k w, for each point whose Euclidean distance to $$$(x, y)$$$ is $$$\sqrt{k}$$$, to increase its weight by $$$w$$$;
• 4 x y k, to query the sum of weights for all points whose Euclidean distances to $$$(x, y)$$$ are $$$\sqrt{k}$$$.

Benecol de Cecco says this question is pretty easy and he asked me to share the problem with you all. By the way, the Euclidean distance between two points $$$(x_0, y_0)$$$ and $$$(x_1, y_1)$$$ is equal to $$$\sqrt{(x_0 - x_1)^2 + (y_0 - y_1)^2}$$$.

A graph without loops or multiple edges is known as a simple graph.

A vertex-colouring is an assignment of colours to each vertex of a graph. A proper vertex-colouring is a vertex-colouring in which no edge connects two identically coloured vertices.

A vertex-colouring with $$$n$$$ colours of an undirected simple graph is called an $$$n$$$-rainbow colouring if every colour appears once, and only once, on all the adjacent vertices of each vertex. Note that an $$$n$$$-rainbow colouring is not a proper colouring, since adjacent vertices may share the same colour.

An undirected simple graph is called an $$$n$$$-rainbow graph if the graph can admit at least one legal $$$n$$$-rainbow colouring. Two $$$n$$$-rainbow graphs $$$G$$$ and $$$H$$$ are called isomorphic if, between the sets of vertices in $$$G$$$ and $$$H$$$, a bijective mapping $$$f: V(G) \to V(H)$$$ exists such that two vertices in $$$G$$$ are adjacent if and only if their images in $$$H$$$ are adjacent.

Your task in this problem is to count the number of distinct non-isomorphic $$$n$$$-rainbow graphs having $$$2 n$$$ vertices and report that number modulo a prime number $$$p$$$.

Recently, my little sweetheart started to ignore me again. I was not sure this time if it's thanks to the agony of a long-distance relationship. So I flew to her city. Nothing changed. Alright, I bet you pray to God that even though you ignore me I still love you. But this seems like strange reasoning to me, as relationships are hard enough even without a $$$16000$$$-mile gap between you and me.

As Stephanie Coontz put in her book 'Marriage, a History':

She argues that the historical shift in emphasis to romantic love is related to the decline of religion, the precariousness of work situations, and the tendency of people to move about geographically rather than remaining in one place. However, an inevitable tension here exists because we are also living in a time which emphasises individuality, autonomy and reaching our personal goals. This means that old rules around rigid gender roles in relationships no longer apply. As sociologists put it:

Back to my personal question, I quantize the individualities, autonomies and personal goals for my little sweetheart and myself to non-negative integers, denoted by $$$I_{girl}, A_{girl}, G_{girl}$$$ and $$$I_{boy}, A_{boy}, G_{boy}$$$ respectively. A brilliant mathematical model that will save my love gives the following formula to measure the distance between the heart of my little sweetheart and mine:

$$$$$$distance(boy, girl) = \max\{|I_{boy} - I_{girl}|, |A_{boy} - A_{girl}|, |G_{boy} - G_{girl}|\} \oplus I_{boy} \oplus A_{boy} \oplus G_{boy} \oplus I_{girl} \oplus A_{girl} \oplus G_{girl},$$$$$$

where $$$\max\{S\}$$$, $$$|x|$$$ and $$$\oplus$$$ correspond to the maximum value in $$$S$$$, the absolute value of $$$x$$$ and the bitwise exclusive-OR operator respectively.

Sadly, it is hard to get these precise values and what I have now are their upper bounds. That is to say, they satisfy the following restrictions:

$$$$$$0 \le I_{girl} \le UI_{girl}, 0 \le A_{girl} \le UA_{girl}, 0 \le G_{girl} \le UG_{girl}$$$$$$

and

$$$$$$0 \le I_{boy} \le UI_{boy}, 0 \le A_{boy} \le UA_{boy}, 0 \le G_{boy} \le UG_{boy}.$$$$$$

Any value of them can be all integers in its restriction with the same probability. Now I need your help to calculate the expected distance between the hearts of the still amorous couple that we are. Please feedback the product between $$$(1 + UI_{boy}) (1 + UA_{boy}) (1 + UG_{boy}) (1 + UI_{girl}) (1 + UA_{girl}) (1 + UG_{girl})$$$ and the expected distance (which must be an integer).

In the C++ language, the values of variables are stored somewhere in the computer memory as zeros and ones. Our program does not need to know the exact location where a variable is stored since one can simply refer to it by its name.

What the program needs to be aware of is the kind of data stored in every variable. Storing a simple integer is not the same as storing a letter or a large floating-point number. Even though they are all represented by zeros and ones, they are not interpreted in the same way, and in many cases, they don't occupy the same amount of memory.

Fundamental data types, implemented directly by the language, represent the basic storage units supported natively by most systems. They can be mainly classified into four types.

Character types: They can represent a single character, such as 'A' or '$'. The most basic type is char, which is a one-byte character.

Numerical integer types: They can store a whole number value, such as $$$7$$$ or $$$1024$$$. They exist in a variety of sizes. The most basic one is int, which is a four-byte integer. long long is a larger one which occupies twice as many memories as int does. A wider type of integer __int128 may appear in some new systems, which is a $$$16$$$-byte integer and rarely useful.

Floating-point types: They can represent real values, such as $$$3.14$$$ or $$$0.01$$$, with different levels of precision, depending on which of the three floating-point types is used. float, double and long double correspond to int, long long and __int128 where the former types hold the same amount of memory as the latter types used respectively.

Boolean type: The boolean type, known in C++ as bool, can only represent one of two states, true or false. It is a one-byte type.

Now you have a code in C++, $$$n$$$ lines of which apply several variables and arrays. Also, I have checked it so I can claim that all variables and arrays in this code are global without any conflicts.

As a novice, each line in your code may only apply for one variable or one array; all types of these variables and arrays are mentioned above; any other types unmentioned can not appear in the code. Your task in this problem is to calculate the number of memories in total that the code is using. Output your answer in Kibibyte ($$$1$$$ Kibibyte is $$$1024$$$ bytes) and round it up to the nearest integer.

Tonight $$$n$$$ young men are going to participate in Peter's campfire party. They decide to play an ancient counting-out game which was first described by Titus Flavius Josephus. Here is a brief introduction to the game.

Before starting the game, these young men will stand in a circle around the campfire and the first man to join the circle will start the game. Counting will begin at the first man and proceed around the circle in the counterclockwise direction repeatedly. That is, the first man will report one at the beginning, and the second one in the counterclockwise direction will report two, and so forth, until a poor man reports $$$k$$$ and consequently leaves the circle to become a bystander. The game will be repeated with the remaining men, restarting from the next man in the counterclockwise direction who will be the new first man, going in the same direction, until all the young men have left the circle.

Peter wanna be the $$$m$$$-th one who left the circle since he strongly believes this number is lucky for him. As a sophisticated programmer, can you point out the right place he should stand at before the game start so that he can achieve his goal?

For the sake of clarity, we assume the index of the first man to join the circle is $$$1$$$, the index of the next man in his counterclockwise direction is $$$2$$$, and so on. By the definition, the index of the last man in that direction should be $$$n$$$, and your task is to determine the index of the place Peter wants.

Edward is a worker for Aluminum Cyclic Machinery. His work is to control the mechanical arms to cut out some parts of the mould material. Here is a brief introduction to his work.

Suppose the operation panel for him is a Euclidean plane with the coordinate system. Originally the mould is a disc whose centre coordinates is $$$(0, 0)$$$ and of radius $$$R$$$. Edward controls $$$n$$$ different mechanical arms to cut out and erase those all of the mould within their affected areas. The affected area of the $$$i$$$-th mechanical arm is a circle whose centre coordinate is $$$(x_i, y_i)$$$ and of radius $$$r_i$$$. In order to obtain the highly developed product, it is guaranteed that the affected areas of any two mechanical arms share no intersection and no one has an affected area containing the whole original mould.

Your task is to determine the diameter of the residual mould. Here the diameter of a subset, which may not be convex, over the Euclidean plane is the supremum (i. e. the least upper bound) of distances between every two points in the subset. Here is an illustration of the sample.

Nancy used to be known for its Art Nouveau quarter, the rum baba and good King Stanislas Leszczynski, the deposed Polish king who gave the city its gorgeously frilly architectural centrepiece in the 18th century.

But in 2013, Nancy rediscovered its Renaissance past, with events and exhibitions all around town this summer, from the fine art museum to the thermal establishment and the botanical gardens. Now it is time for me to discover the old town's Renaissance relics and the Utopian town-planning schemes of Duke Charles III, from the days when Nancy was capital of a powerful independent duchy at the crossroads between northern and southern Europe.

The old and new towns are seamlessly connected today. The new city or Ville Neuve laid out in 1588 is still the commercial heart of the city with its shops and banks, and covered by food markets in the street near the square originally planned for the cathedral.

In this autumn, I have the privilege of spending a several-months-long holiday in Ville Neuve. Daily contemplations always follow the breakfasts together with baguettes' sweet and smooth. What makes a baguette better is not La vache qui rit cheese, but where I get it. But why should people who program computers be so concerned about the number of food markets in a street? I do label those food markets which supply baguettes in the street from $$$1$$$ to $$$n$$$.

At each glimmering daybreak came, I carry several one-euro coins and make a plan to visit several consecutive food markets. Regardless of winds and rains, a food market always offers a fixed number of baguettes at a fixed price. Two different food markets may be different: The numbers of their daily baguettes offered and the prices differ.

The early bird catches the worm. Since there is no need to worry about other customers, enough money makes me free to buy all the baguettes in a food market or be blind and go to the next market.

But why should people just like you be so concerned about the number of different ways that I have to purchase baguettes? They even double-check with me that I may cost nothing and starve, or spend any amount of money that I have. As what theorists always say in a knapsack-like problem, two ways to purchase baguettes are different if, at some markets, the numbers of baguettes purchased vary.

A man who pursuits high efficiency like you tries to tell me the number of ways I have once he confirmed the amount of money I carry and my visit plan day after day. An undisciplined man like me, though I have made a long list of plans for all days, decides to make a new plan for the next day once I received your reply about one day. I use $$$lastans$$$ to denote the number in your reply and set it to zero before my first day in Ville Neuve.

On a day, I check what I made in the original plan, say $$$l'$$$ and $$$r'$$$ the index of the first food market I decided to visit, and of the last one, and say $$$c$$$ the number of one-euro coins I decided to carry. A transformation like an encryption

$$$$$$l = \min\{((l' + lastans) \bmod n) + 1, ((r' + lastans) \bmod n) + 1\}$$$$$$

and

$$$$$$r = \max\{((l' + lastans) \bmod n) + 1, ((r' + lastans) \bmod n) + 1\}$$$$$$

shows me a new plan, where $$$\min\{x, y\}$$$ and $$$\max\{x, y\}$$$ correspond to the minimum and the maximum of $$$x$$$ and $$$y$$$ respectively, and that is what I execute this morning. You need to tell me the number you calculate for this day and I will set $$$lastans$$$ to your reply in modulo $$$(10^9 + 7)$$$.