Hello everyone! I am your old friend Rikka. Welcome to Xuzhou. This is the first problem, which is a problem about the minimum spanning tree (MST). I promise you all that this should be the easiest problem for most people.

A minimum spanning tree, or minimum weight spanning tree, is a subset of edges from an edge-weighted undirected graph, which forms a tree with the minimum possible total edge weight that connects all the vertices together without any cycles.

In this problem, Rikka wants you to calculate the summation of total edge weights through all MSTs for a given graph, which obviously equals to the product of the total edge weight in an MST and the total number of different MSTs. Note that two spanning trees are different if the sets of their edges are different. In addition, a disconnected graph could have no MSTs, the number of whose different MSTs is zero.

To decrease the size of the input, Rikka provides an edge-weighted undirected graph via a random number generator with given random seeds, denoted by two integers $$$k_1$$$ and $$$k_2$$$. Supposing the number of vertices and edges in the graph are $$$n$$$ and $$$m$$$ respectively, the following code in C++ tells you how to generate the graph and store the $$$i$$$-th edge between the vertex $$$u[i]$$$ and $$$v[i]$$$ with weight $$$w[i]$$$ in corresponding arrays. You can use the code directly in your submissions.

Also, to decrease the size of the output, your code should output the answer modulo $$$(10^9 + 7)$$$.

If you have already learned how to handle that, start your show and omit all the rest of the statement.

To make sure everyone knows how to solve this problem, here Rikka would like to provide for you all an effective practice which can solve the problem and help you all get Accepted!

The first one you need to know is the Kirchhoff's matrix tree theorem. Given an undirected graph $$$G$$$ with $$$n$$$ vertices excluding all loops, its Laplacian matrix $$$L_{n \times n}$$$ is defined as $$$(D - A)$$$, where $$$D$$$ is the degree matrix and $$$A$$$ is the adjacency matrix of the graph. More precisely, in the matrix $$$L$$$ the entry $$$l_{i, j}$$$ ($$$i \ne j$$$) equals to $$$-m$$$ where $$$m$$$ is the number of edges between the $$$i$$$-th vertex and the $$$j$$$-th vertex, and $$$L_{i, i}$$$ equals to the degree of the $$$i$$$-th vertex. Next, construct a matrix $$$L^{*}$$$ by deleting any row and any column from $$$L$$$, for example, deleting row $$$1$$$ and column $$$1$$$. The Kirchhoff's matrix tree theorem shows that the number of spanning trees is exactly the determinant of $$$L^{*}$$$, which can be computed in polynomial time.

Now let me explain an algorithm that counts the number of MSTs. The algorithm breaks up the Kruskal's algorithm for MST into a series of blocks, each of which consists of a sequence of operations about adding edges in a same weight into a multigraph (where a multigraph is a graph, two vertices of which may be connected by more than one edge) whose vertices are components that have been built through the previous block of operations.

Precisely speaking, let's label the multigraph that has been built after the $$$i$$$-th block of operations as $$$G_i$$$. Without loss of generality, let's consider the $$$0$$$-th block which has no operation and let $$$G_0$$$ be an empty graph with $$$n$$$ isolated vertices. The $$$i$$$-th block of operations squeezes vertices in $$$G_{i - 1}$$$ connected by edges in this block into a single vertex. The result is exactly the graph $$$G_i$$$.

If you know the cardinal principle of Kruskal's algorithm pretty well, you may find that the number of MSTs is the product of the numbers of spanning trees in every component of the graph for each block-defining weight. Actually, the number of edges for a certain weight is fixed in all MSTs, based on the greedy-choice strategy in Kruskal's algorithm. Finally, the Kirchhoff's matrix tree theorem helps you compute the numbers of spanning trees for graphs.

Several years of ACM-ICPC experience enables Rikka, as a student at Keping University, to catch the tide of the algorithm development.

Over the courses for this semester, Rikka made a deep study of line graphs. In the mathematical discipline of graph theory, the line graph of a simple undirected graph $$$G$$$ is another simple undirected graph $$$L(G)$$$ that represents the adjacency between every two edges in $$$G$$$. Precisely speaking, for an undirected graph $$$G$$$ without loops or multiple edges, its line graph $$$L(G)$$$ is a graph such that

• each vertex of $$$L(G)$$$ represents an edge of $$$G$$$; and
• two vertices of $$$L(G)$$$ are adjacent if and only if their corresponding edges share a common endpoint in $$$G$$$.

Given a simple undirected graph $$$G$$$, Rikka's study aims to count the number of vertices in its line graph. Now she decides to show you some critical results of her early study, concerning the number of vertices in the line graph of $$$G$$$, $$$L(G)$$$, the line graph of the line graph of $$$G$$$, $$$L^2(G)$$$ (i. e. $$$L(L(G))$$$), and so forth, denoted by $$$|V(L(G))|$$$, $$$|V(L^2(G))|$$$, $$$\cdots$$$.

By the definition of an undirected graph with $$$n$$$ vertices and $$$m$$$ edges, we know that

$$$$$$|V(L(G))| = \sum_e 1 = m = \frac{1}{2} \sum_u d_1(u),$$$$$$

where $$$d_1(u)$$$ represents the degree of vertex $$$u$$$ in $$$G$$$.

Once we know how to count, for any edge $$$e$$$ in $$$G$$$, the number of edges which share a common endpoint with $$$e$$$, or equally speaking the degree of $$$e$$$ in $$$L(G)$$$, which is denoted by $$$d'_1(e)$$$, we have

$$$$$$|V(L^2(G))| = \frac{1}{2} \sum_e d'_1(e) = \frac{1}{2} \sum_{e = (u, v)} (d_1(u) - 1 + d_1(v) - 1) = \frac{1}{2} \sum_{u} d_1(u) (d_1(u) - 1).$$$$$$

A similar easy analysis can help us to calculate $$$|V(L^3(G))|$$$, and an excellent result in Rikka's known work, which was published in the 2018 JheZiang Olympiad in Informatics, reveals the number of vertices in $$$L^4(G)$$$ as

$$$$$$\begin{aligned}|V(L^4(G))| = \frac{1}{2} \sum_{u} &(2 d_1^2(u) - 13 d_1(u) + 21 + 4 d_2(u)) d_1(u) (d_1(u) - 1) \\ &-13 (d_1(u) - 1) d_2(u) + (d_1(u) - 2) d_{2, 2}(u) + d_2^2(u),\end{aligned}$$$$$$

where $$$d_2(u)$$$ is the summation of degrees of all adjacent vertices of $$$u$$$ in $$$G$$$, and when considering the degrees squared of all adjacent vertices of $$$u$$$, $$$d_{2, 2}(u)$$$ is the summation of them all.

Based on the equation $$$L^5(G) = L^4(L(G))$$$, her newest work made a further development. She extrapolates from the result about $$$L^4(G)$$$ a linear computable method to calculate the number of vertices in $$$L^5(G)$$$ in time complexity $$$O(n + m)$$$. Rikka pointed out that the data about vertices required in the summation form of $$$|V(L^4(G))|$$$ imply new data about edges with similar definitions. Actually, the relationship between $$$d_1$$$ and $$$d'_1$$$ is the easiest correspondence. A harder one is described as the one between $$$d_2$$$ and $$$d'_2$$$. Luckily, we can calculate all these new data which we need about the edges in linear time. Thus an attempt replacing the summation of vertices by a summation of edges provides a strict formula for the number of vertices in $$$L^5(G)$$$.

Now you must try to go with the current of the times. In this problem, for an undirected simple graph $$$G$$$, you are asked to calculate the number of vertices in $$$L^6(G)$$$ and output the number modulo $$$(10^9 + 7)$$$.

On the way to the Moscow, Rikka knows someone will replace her. Who is the guy? A devil to get in touch with her dark side, or an angel to rinse the shadow off her mind? However, Rikka knows that her successor has a special name, whose meaning in Chinese is Consistency. The process of replacement is so wonderful and sentimental, which is what you all must know.

Now, the only road from Beijing to Moscow is described as a broken line with $$$n$$$ segments in the $$$X$$$-$$$H$$$ plane. The $$$i$$$-th segment connects the points $$$(i - 1, h_{i - 1})$$$ and $$$(i, h_i)$$$, and $$$h_0 = h_n = 0$$$ are known. This figure is a topographic map showing the whole trip from Beijing to Moscow and its $$$H$$$ axis indicates the altitude. The distance of a path between two points is the length of the broken line between their corresponding points in the map.

At the outset of the trip, Rikka is in Beijing whose location in the $$$X$$$-$$$H$$$ plane is $$$(0, 0)$$$; Consistency, the guy who will replace Rikka, is in Moscow which is located at $$$(n, 0)$$$. Consistency always maintains consistent academic standards, a consistent life level, a consistent height of perspective and the altitude as what Rikka owns. This is why their heights are the same yesterday, today and forever.

Now Rikka wants you to calculate the minimum total distance they need (which is the total length of paths that Rikka and Consistency travel along). By the time that Rikka arrives in Moscow and Consistency arrives in Beijing as well, their replacement will be finished (and this is the ending which is also a new beginning).

For a known sequence, counting subsequences with a certain remarkable property can depict the sequence itself to a certain extent.

Now, Rikka has a sequence $$$A$$$ of length $$$n$$$ whose elements, denoted by $$$a_1, a_2, \cdots, a_n$$$, are positive integers in $$$[1, n]$$$. A bridging relation matrix (BRM) is a $$$n \times n$$$ logical matrix with elements from $$$\{0, 1\}$$$. Here Rikka defines a Yuta subsequence based on a given BRM, $$$M = (M_{i, j})_{1 \le i, j \le n}$$$.

Rikka calls a subsequence of $$$A$$$, denoted by $$$a_{p_1}, a_{p_2}, \cdots, a_{p_m}$$$ with $$$m\ge 1$$$ and $$$1 \le p_1 \lt p_2 \lt \cdots \lt p_m \le n$$$, a Yuta subsequence if and only if $$$M_{a_{p_i}, a_{p_{i + 1}}} = 1$$$ for $$$i = 1, 2, \cdots, m - 1$$$. Counting the number of different Yuta subsequences has a profound value in data analysis and data recovery.

Rikka thinks this task is too simple and she wants to make it look harder and more heuristic. Rikka knows that a Yuta subsequence may appear in the sequence $$$A$$$ several times and top programmers may use something like map<vector<int>, bigInt> cnt in C++ or Map<ArrayList<Integer>, BigInteger> cnt in Java to store all Yuta subsequences and count the numbers.

She calls the sum of the cubes of the numbers of occurrences for all Yuta subsequences, which is equal to the sum of cubes of all the second elements in cnt, the third coefficient of $$$A$$$ over $$$M$$$.

Now, after showing you the sequence and the BRM, she wants you to calculate the third coefficient of the sequence over the given BRM in modulo $$$(10^9 + 7)$$$.

As we know, Rikka is poor at data structures. Yuta is worrying about this situation, so he gives Rikka some tasks about data structures to practice. Here is one of them:

Yuta has an array $$$A$$$ with $$$n$$$ numbers, denoted by $$$A[1], A[2], \cdots, A[n]$$$. Then he makes $$$m$$$ operations on it.

There are three types of operations:

• 1 l r k: for each index $$$i$$$ in $$$[l, r]$$$, change the value of $$$A[i]$$$ into $$$(A[i] + k)$$$;
• 2 l r k: for each index $$$i$$$ in $$$[l, r]$$$, change the value of $$$A[i]$$$ into $$$k$$$;
• 3 l r x: Yuta wants Rikka to count the number of different indices $$$y$$$ with $$$l \le y \le r$$$ such that $$$\max\{A[\min\{x, y\}], A[\min\{x, y\}+1], \cdots, A[\max\{x, y\}]\} = \max\{A[x], A[y]\}$$$.

It is too difficult for Rikka. Can you help her?

As we know, Yuta is poor at counting numbers. Rikka is worrying about this situation, so she gives Yuta some counting tasks to practice. Here is one of them:

In computer programming, a string is traditionally a sequence of characters and a substring of a string is a contiguous sequence of characters within the string. For instance, snowball is a string, now is a substring of snowball and bow is not a substring of snowball. Moreover, the concatenation of two strings $$$U$$$ and $$$V$$$ is named as $$$U V$$$, that is, if $$$U$$$ is snow and $$$V$$$ is ball, then $$$U V$$$ is snowball.

Rikka has a string $$$S$$$ of length $$$n$$$ and she wants Yuta to count how many distinct nice strings in total. Here, she calls a non-empty string $$$T$$$ nice if

• $$$T$$$ is a substring of $$$S$$$; and
• $$$T P$$$ is not a substring of $$$S$$$ for any non-empty string $$$P$$$ meeting the condition that $$$T P$$$ and $$$P T$$$ are the same string.

It is too difficult for Yuta. Can you help him?

Rikka has a tree $$$T$$$ with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$.

Meanwhile, Rikka has marked $$$m$$$ simple paths in $$$T$$$, the $$$i$$$-th of which is between the vertices $$$x_i$$$ and $$$y_i$$$, where some of them could be the same path.

Now, Rikka wants to know in how many different strategies she can select $$$k$$$ paths from the marked paths such that those selected paths share at least one common vertex.

Blue, the colour of the sky, the sea and your eyes.

Green, the colour of nature, fertility and life.

Purple, the colour of good judgment, and of people seeking spiritual fulfilment.

Orange, the only colour that is also a fruit.

Yellow, the colour in smiley faces.

Red, the warmest of all.

Rikka loves them all, but what is her favourite colour? She has found $$$k$$$ different colours, numbered from $$$1$$$ to $$$k$$$, and she knows that the best colour should be the one after mixing them all together. The best colour is called the DREAM.

Rikka has also prepared a long and narrow colour palette of length $$$10^9$$$. She designates $$$n$$$ segments in the palette. A segment described by two integers $$$l$$$ and $$$r$$$ ($$$0 \le l \lt r \le 10^9$$$) represents an area of the palette where the distance between the leftmost end of the palette and the left endpoint (resp. the right endpoint) of the area is $$$l$$$ (resp. $$$r$$$).

She will for each segment designated smear the pigment of any of these colours (from $$$1$$$ to $$$k$$$) which she has found evenly on it. Some areas may contain pigments of several different colours, since these segments may intersect. If some areas contain all these $$$k$$$ different colours which she has found, it would blend into the DREAM.

Now, Rikka wants you to maximize the total length of all areas in the palette such that each part of them can blend into the DREAM. You also need to provide a feasible plan.

Rikka knows that Bubble sort is a simple but beautiful algorithm, Quicksort is a complex but efficient algorithm, and Shellsort is a weird but practical algorithm. Rikka is interested in all sorting algorithms and she can assign as many new problems for ICPC contests as she wants.

Rikka hates those guys who create new problems with the same ideas over and over again, and she hopes not to become the person she hates to be. Though she has already assigned several problems for sorting algorithms such as Merge sort and Insertion sort, she decides to show you the last problem about sorting algorithms to end this series forever.

Here Rikka introduces the sorting network and she defines a comparator at first. For a permutation $$$A$$$ of the $$$n$$$ smallest positive integers denoted by $$$a_1, a_2, \cdots, a_n$$$, a comparator $$$[u, v]$$$ ($$$u \ne v$$$) sorts the $$$u$$$-th and the $$$v$$$-th element in $$$A$$$ into nondecreasing order. Formally, a comparator is a mapping $$$[u, v]$$$ satisfying

• $$$[u, v](a_u) = \min(a_u, a_v)$$$; and
• $$$[u, v](a_v) = \max(a_u, a_v)$$$; and
• $$$[u, v](a_k) = a_k$$$ for all $$$k$$$ with $$$k \ne u$$$ and $$$k \ne v$$$.

Rikka defines a sorting network as a composition of comparators and provides for you a sorting network with $$$k$$$ ordered comparators. Now, Rikka wants you to count the number of permutations of $$$1$$$ to $$$n$$$ which, through the given sorting network, would become an almost sorted permutation. She says a permutation of $$$1$$$ to $$$n$$$ is almost sorted if the length of its longest increasing subsequence is at least $$$(n - 1)$$$.

Rikka discovered an unnamed ancient temple together with its internal map by accident. The temple contains $$$n$$$ separated rooms. Several one-way roads connect these rooms and form a directed acyclic graph.

When a visitor enters the temple, she will appear in the first room. she can find the exit of the temple in the $$$n$$$-th room. Notice that she probably cannot arrive all rooms from the entrance and meanwhile, she may not have the chance to escape the temple from some room inside.

All rooms have some treasures. The weight of the treasure stored in the $$$i$$$-th room is $$$w_i$$$, and its value is $$$c_i$$$. A visitor, when she arrives at the exit, is allowed to leave the temple if the remainder of the total weight of treasures she has picked divided by $$$k$$$ is equal to $$$t$$$ where $$$k$$$ and $$$t$$$ are fixed integers.

Besides, a guardian is standing in a room and protecting the treasure, but no one knows where she is. To prevent being attacked, visitors should not step into the room of the guardian at any time.

Now Rikka decides to visit the unnamed temple. She will select a path from the entrance to the exit, picking treasures in all rooms she will pass through. She wants you to calculate, for each index $$$i$$$ from $$$1$$$ to $$$n$$$, what the maximum total value she can obtain is and in how many ways she could achieve that, in case the guardian is standing in the $$$i$$$-th room.

Every time when Rikka faces to a great nature sight, she will recall a line of ants moving in a hurry. Rikka loves ants and keeps two large colonies of ants in her drawer. Observing ants hurrying in moving has controlled her life.

That is why she prepares $$$n$$$ different nests in her drawer, and $$$n$$$ undirected channels between these nests form a circular orbit. All nests are numbered by $$$1$$$ to $$$n$$$ in order, and the lengths of channels are known. The first colony of ants is living in the $$$s_1$$$-th nest, and the second colony is living in the $$$s_2$$$-th nest.

Now, ants decide to move to new nests together. The new home for these two colonies of ants will be the $$$e_1$$$-th nest and the $$$e_2$$$-th nest respectively.

For each colony, all ants should queue up one by one to crawl from the origin to the destination along a path. They cannot be split into several groups crawling moving along different paths. Then, they can measure the complexity of their plan moving to new nest using the total length of channels in the path selected.

If these two colonies of ants select paths sharing some common channels, they will walk through these channels slowly for security. Specifically, for each common channel, we can consider equivalently that its measured length will be tripled.

Ants are highly intelligent and they all want to minimize the complexities of their plan. They will choose the best strategies for themselves respectively without negotiation. All they know are the lengths of channels, and the nests where their colony and the other one will start and end respectively.

Rikka wants you to calculate the expected complexities of plans for each colony of ants. For more details about the best strategy, please refer to note.

A two-dimensional grid graph, also known as a square grid graph, is an undirected graph with $$$n m$$$ vertices corresponding all nodes in a $$$n \times m$$$ grid. An edge here is an abstract description for a matchstick of length one in the grid connecting two adjacent nodes.

Now, Rikka gives you a $$$n \times m$$$ grid graph made with no more than $$$(2 n m - n - m)$$$ edges. She wants you to calculate the number of different orientations for the undirected graph such that the oriented graph is a directed graph with no directed cycles.

In this problem, an orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph.

Rikka loves convex polygons, so she decides to install some illuminants to embellish polygons.

Now she has a large convex polygon with $$$n$$$ sides. She also has $$$m$$$ different points strictly outside the polygon which are all legal positions to install illuminants.

An illuminant can light up some exterior boundaries of the polygon.

Rikka wants to install some illuminants to light up all exterior boundaries of the polygon. She asks you to calculate the least number of illuminants which she needs and provide a feasible scheme.