M - Marblecoin

Time limit: 3 seconds
Memory limit: 256 megabytes
Languages: MS C# .NET 4.7.2053,GNU G++11 5.1.0 ...

Cubiconia is known for having one of the highest tax rates. Taxes are calculated on a daily basis and even things that seem worthless are subject to taxes. In order to avoid the crazy tax rates, some of the emperor’s friends created a new currency using marbles. Unfortunately, it didn’t work out, marbles became subject to taxes as well.

Despite this, the emperor believes that using marbles as a currency is a great idea and that in the future they will be worth a lot more. So he decided to steal all of his friends’ marbles. To avoid unnecessary attention, in the dead of each night he will visit one of his friends and during each visit exactly one marble will be stolen. Since the emperor’s friends keep their marbles in stacks, only a marble that is currently on the top of a stack might be stolen.

Each marble has a value associated to it. The amount due per owned marble is $V \times 365^D$, where $V$ is the value associated to the marble and $D$ is the number of days the marble was owned. The emperor plans to sell all the marbles once he is finished stealing them. This means that, if there is a total of $T$ marbles, the marble owned the least amount of time will be owned for $1$ day, while the one owned the maximum amount of time will be owned for $T$ days.

The emperor is smart and already realized that the total due in taxes depends on the order in which marbles are stolen. To avoid paying more taxes than necessary, he would like to know the best order to steal the marbles. Can you help him?

Input

The first line contains an integer $N$ $(1 \leq N \leq 10^5)$ representing the number of stacks the emperor is going to steal from. Each of the next $N$ lines describes a stack with an integer $K$ $(1 \leq K \leq 10^5)$ followed by $K$ integers $V_1, V_2, ..., V_K$ ($1 \leq V_i \leq 300$ for $i = 1, 2, ..., K$); the number $K$ is the amount of marbles in the stack, while the numbers $V_1, V_2, ..., V_K$ are the values of the marbles in the stack, from top to bottom. The total amount of marbles is at most $4 \times 10^5$.

Output

Output a single line with an integer representing the minimum value due in taxes if the marbles are stolen in an optimal order. Because this number can be very large, output the remainder of dividing it by $10^9 + 7$.

Sample test(s)

Input
3 1 1 1 2 1 3
Output
48894670
Input
3 3 2 5 7 4 1 4 6 10 3 3 2 1
Output
227712621