hackercupai/hackercup huggingface dataset:
The market is hot for geological talent! Hiring agents are competing to display their job flyers on street intersections across \(T\) towns.

A town's streets can be represented as an infinite 2D grid with rows numbered by increasing integers from North to South and columns numbered by increasing integers from West to East.

There are \(N\) hiring agents, numbered from \(1\) to \(N\). Agent \(i\) starts at the intersection of row \(R_i\) and column \(C_i\), holding \(P_i\) flyers, and facing the cardinal direction \(D_i\) (`"N"` for North, `"S"` for South, `"E"` for East, or `"W"` for West). Each *turn* taken by an agent consists of the following:

1. Post one of their own flyers at their current intersection, shredding any competing flyer that may have previously been there.
2. If the agent has more flyers, move to the adjacent intersection in direction \(D_i\).

The agents will take turns posting one flyer at a time. Agent \(1\) will take a turn, followed by agent \(2\), and so on until agent \(N\) takes a turn, at which point agent \(1\) will go again (if necessary). Note that there may be multiple agents occupying the same intersection at any point in time.

Let \(F_i\) be the number of flyers placed by agent \(i\) which remain will unshredded at the end. Your job is to compute the sum of \(i * F_i\) over all agents \(i\). As this sum may be very large, you should only compute it modulo \(1{,}000{,}000{,}007\).

# Constraints

\(1 \le T \le 75\)
\(1 \le N \le 800{,}000\)
\(0 \le R_i, C_i \le 1{,}000{,}000{,}000\)
\(1 \le P_i \le 1{,}000{,}000{,}000\)
\(D_i \in \{\)`"N"`, `"S"`, `"E"`, `"W"`\(\}\)

The sum of \(N\) across all towns is at most \(2{,}000{,}000\).

# Input

Input begins with an integer \(T\), the number of towns. For each town, there is first a line containing a single integer \(N\). Then, \(N\) lines follow, the \(i\)th of which consists of \(3\) space-separated integers \(R_i\), \(C_i\), and \(P_i\), followed by a space-separated character, \(D_i\).

# Output

For the \(i\)th town, print a line containing *"Case #i: "* followed by a single integer, the sum of \(i * F_i\) over all agents \(i\), modulo \(1{,}000{,}000{,}007\).

# Sample Explanation

In the first town, the relevant portion of the grid will end up with the following flyers (with `"."` representing an intersection with no flyer), yielding an answer of \((1 * 3 + 2 * 2 + 3 * 1 + 4 * 1) \;\mathrm{mod}\; 1{,}000{,}000{,}007 = 14\):

{{PHOTO_ID:1597395337265553|WIDTH:180}}

In the second town, the relevant portion of the grid will end up with the following flyers, yielding an answer of \((1 * 2 + 2 * 2 + 3 * 2 + 4 * 2) \;\mathrm{mod}\; 1{,}000{,}000{,}007 = 20\):

{{PHOTO_ID:4543454065770744|WIDTH:234}}

In the third town, each of agent \(2\)'s turns will involve shredding the last flyer placed by agent \(1\) and replacing it with her own. This will result in \(1{,}000{,}000{,}000\) intersections containing agent \(2\)'s flyers, for an answer of \((2 * 1{,}000{,}000{,}000) \;\mathrm{mod}\; 1{,}000{,}000{,}007 = 999999993\).

In the fourth town, the relevant portion of the grid will end up with the following flyers:

{{PHOTO_ID:451563133198975|WIDTH:360}}