PROBLEM STATEMENT
Limak is a grizzly bear.
He is currently making plans to attack Deerland.

Deerland has N cities, numbered from 0 to N-1.
The cities are all connected together by a network of roads.
There are exactly N-1 bidirectional roads, each connecting two cities.
(Hence, the topology of Deerland is a tree.)

Limak will attack each city in Deerland exactly once.
For each i, when he attacks city i, there are two possible outcomes:

With probability 1/(i+1) the city will defend itself successfully.
In all other cases the city is destroyed by Limak. The city disappears from Deerland, along with 
all roads that led into the city.


Let's define a region as a connected component of Deerland.
In other words, a region is a maximal group of cities such that the existing roads allow us to 
travel between any two cities in the group.
Initially, the entire Deerland is a single region.
After Limak's N attacks Deerland will be divided into one or more regions.

The strength of a region is the square of the number of cities it contains.

You are given a description of Deerland in a format that is specified below.
Let E be the expected value of the sum of strengths of all regions after Limak attacks Deerland.
It can be proved that E*N! is an integer.
Return this integer modulo 1,000,000,007.

The description of Deerland is provided in the form of a pseudorandom generator.
You are given the ints N, R0, A, B, M, LOW, and HIGH.
As defined above, N is the number of cities in Deerland.
The list of roads is generated by the pseudocode below.


R = R0;
BILLION = 1000000000;
for i between 1 and N-1, inclusive:
    R = (A * R + B) modulo M;
    MIN = ((i-1) * LOW)  / BILLION;
    MAX = ((i-1) * HIGH) / BILLION;
    there is a road between city i and city MIN + (R modulo (MAX-MIN+1));


Both divisions in the pseudocode are integer divisions.
(Integer division rounds down. For example, 29/10 is 2.)
You may assume that the pseudocode always generates a valid tree.
Watch out for integer overflow when implementing it.

DEFINITION
Class:BearAttacks
Method:expectedValue
Parameters:int, int, int, int, int, int, int
Returns:int
Method signature:int expectedValue(int N, int R0, int A, int B, int M, int LOW, int HIGH)


CONSTRAINTS
-N will be between 1 and 1,000,000, inclusive.
-M will be between 1 and 1,000,000,000, inclusive.
-R0, A and B will be between 0 and M-1, inclusive.
-LOW and HIGH will be between 0 and 1,000,000,000, inclusive.
-LOW will not be greater than HIGH.


EXAMPLES

0)
3
0
2
3
100
938593850
1000000000

Returns: 21

There are N=3 cities.
The generator outputs that the two roads are 1-0 and 2-1.
Hence, Deerland is the path 0-1-2.
Here is what may happen:

With probability (1/1) * (1/2) * (1/3) = 1/6 all three cities survive. In this case we have a 
single region with strength 9.
With probability (1/1) * (1/2) * (2/3) = 2/6 only cities 0 and 1 survive. We have one region with 
strength 4.
With probability (1/1) * (1/2) * (1/3) = 1/6 only cities 0 and 2 survive. Here we have two 
regions, each with strength 1, hence the total strength is 2.
With probability (1/1) * (1/2) * (2/3) = 2/6 only city 0 survives. There is only one region and 
its strength is 1.

Therefore, the expected sum of regions' strengths is (1/6)*9 + (2/6)*4 + (1/6)*2 + (2/6)*1 = 21/6.
The correct return value is ( (21/6) * N! ) modulo 1,000,000,007, which is 21.

1)
3
0
0
0
1
0
0

Returns: 23

Again there are three cities, but now the roads are 1-0 and 2-0.
A different set of roads leads to a different answer.

2)
6
303840291
848660283
395739574
950123456
0
1000000000

Returns: 3856

Six cities. Roads: 1-0, 2-1, 3-1, 4-3, 5-1.

3)
1
0
0
0
1
0
0

Returns: 1



4)
19
384038999
938592393
692854433
1000000000
300000000
600000000

Returns: 473263988



 This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.