Wilson, everyone's favorite recurring programming contest character, has
finally decided that it's time to retire. Why? After several more job changes
and miraculous promotions, not only has he become incredibly wealthy, but he's
ended up stuck in a boring administrative role, which was the last thing he
wanted!

Wilson is currently employed as the head of accounting at a pie delivery
company, and has been given one last assignment to complete before his
retirement — computing delivery truck gas usage. He wishes he could just drive
one of the trucks instead...

The pie delivery company services a network of **N** \+ 1 towns, which rather
looks like a pie itself (or perhaps like an umbrella...). **N** of the towns
form a circle around the outside of the region, and are numbered from 1 to
**N** in clockwise order. They are connected to one another by **N** roads,
each of which can be driven along in either direction. The _i_th of these
roads requires **Oi** litres of gas to drive along, and runs between towns _i_
and _i_ \+ 1 (unless _i_ = **N**, in which case it instead runs between towns
**N** and 1).

The remaining town, numbered **N** \+ 1, lies in the center of the region.
There are **N** roads connecting it to the other towns, each of which can be
driven along in either direction. The _i_th of these roads requires **Ri**
litres of gas to drive along, and runs between towns **N** \+ 1 and _i_.

A total of **N** * (**N** \+ 1) / 2 pie deliveries are scheduled to be carried
out, one for each distinct pair of towns. In particular, for every town _i_,
_i_ \- 1 deliveries will originate from it, with the _j_th of them having town
_j_ as its destination. The truck drivers will have to pay the gas expenses
out of their own pockets, of course, so for each delivery, the truck driver
will choose a sequence of roads to follow from the initial town to the
destination such that the total amount of gas required for their trip is
minimized. Wilson's task is to tally up the total amount of gas which will be
used across all **N** * (**N** \+ 1) / 2 of the deliveries. He's been
instructed to only determine the value of this sum modulo 1,000,000,007.

You're given **O1**, and **O2..N** may then be calculated as follows using
given constants **Ao**, **Bo**, **Co**, and **Do**.

**Oi** = ((**Ao** * **Oi-1** \+ **Bo**) %**Co** \+ **Do**

You're given **R1**, and **R2..N** may then be calculated as follows using
given constants **Ar**, **Br**, **Cr**, and **Dr**.

**Ri** = ((**Ar** * **Ri-1** \+ **Br**) %**Cr** \+ **Dr**

### Input

Input begins with an integer **T**, the number of different regions of towns.
For each region, there is first a line containing the integer **N**. Then
there is a line with five space-separated integers, **O1**, **Ao**, **Bo**,
**Co**, and **Do**. Then there is a line with five space-separated integers,
**R1**, **Ar**, **Br**, **Cr**, and **Dr**.

### Output

For the _i_th graph, print a line containing "Case #**i**: " followed by the
total amount of gas which will be used (in litres), modulo 1,000,000,007

### Constraints

1 ≤ **T** ≤ 40
3 ≤ **N** ≤ 1,000,000
1 ≤ **O1**, **Co**, **Do** ≤ 1,000,000
0 ≤ **Ao**, **Bo** ≤ 1,000,000
1 ≤ **R1**, **Cr**, **Dr** ≤ 1,000,000
0 ≤ **Ar**, **Br** ≤ 1,000,000

### Explanation of Sample

In the first case, the roads running around the outside require 1, 3, and 5
litres of gas to drive along, respectively. Meanwhile, the roads connected to
the central town require 1, 2, and 2 litres of gas to drive along,
respectively. The amounts of gas required for the 6 deliveries (in litres) are
[1, 1, 2, 2, 3, 3], for a total of 12.