hackercupai/hackercup huggingface dataset:
Facebulk Inc. is a mining company whose Bulk Geological Processing (BGP) network has been disrupted lately. To improve response times in the event of future disruptions, the company plans to assign shift partners within each of its \(T\) ore-processing plants.

A given plant has \(N\) employees, numbered from \(1\) to \(N\) in decreasing order of seniority.

Initially, none of the employees are partners with one another. The company will then assign \(M\) partnerships, one by one, with the \(i\)th partnership pairing up employees \(A_i\) and \(B_i\) if they weren't already. An employee can be part of multiple partnerships.

An employee \(x\) can *directly* receive reports from an employee \(y\) if \(x\) has higher seniority than \(y\) (that is, \(x < y\)), or if \(x\) and \(y\) are partners, or both. An employee \(x\) can *indirectly* receive reports from an employee \(y\) if there exists at least one intermediate employee \(z\) such that \(x\) can directly receive reports from \(z\), and \(z\) can directly or indirectly receive reports from \(y\).

Let \(S_i\) be the number of ordered pairs of employees \((x, y)\) such that employee \(x\) can directly or indirectly receive reports from employee \(y\) after the first \(i\) partnership pairings have been made. Note that \(S_i \le N(N-1)\).

Please help Facebulk evaluate its reporting efficiency over time by computing the product of \(S_{1..M}\). As this product may be very large, you should compute its value modulo \(1{,}000{,}000{,}007\).

# Constraints

\(1 \le T \le 65\)
\(2 \le N \le 2{,}000{,}000\)
\(1 \le M \le 2{,}000{,}000\)
\(1 \le A_i, B_i \le N\)
\(A_i \ne B_i\)

The sum of \(N + M\) across all plants is at most \(10{,}000{,}000\).

# Input

Input begins with an integer \(T\), the number of ore-processing plants. For each plant, there is first a line containing \(2\) space-separated integers, \(N\) and \(M\). Then, \(M\) lines follow, the \(i\)th of which contains 2 space-separated integers, \(A_i\) and \(B_i\).

# Output

For the \(i\)th plant, print a line containing *"Case #i: "* followed by a single integer, the product of \(S_{1..M}\) as defined above, modulo \(1{,}000{,}000{,}007\).

# Sample Explanation

In the first plant, after a partnership between employees \(1\) and \(2\) forms, each employee can receive reports from the other. Therefore, \(S = [2]\), and the answer is \(2 \mathrm{\;mod\;} 1{,}000{,}000{,}007 = 2\).

In the second plant, after a partnership between employees \(3\) and \(2\) forms, employee \(1\) can receive reports from employees \(2\) and \(3\), employee \(2\) can receive reports from employee \(3\), and employee \(3\) can receive reports from employee \(2\). Therefore, \(S = [4]\).

In the third plant, \(S = [7, 12]\). Each employee can receive reports from each other employee after both partnerships have been formed — for example, employee \(2\) can indirectly receive reports from employee \(1\) through employee \(4\). Therefore, the answer is \((7 \cdot 12) \mathrm{\;mod\;} 1{,}000{,}000{,}007 = 84\).

In the fourth plant, \(S = [18, 21, 25, 25]\).

In the fifth plant, \(S = [211, 217, 217, 232, 283]\).