406203: GYM102309 E Expectation of Orz Pandas

The Orz Pandas has $$$n$$$ boxes in a line. Master wang9897 loves to repeat so he would do an operation on the boxes. He chooses a digit $$$x_i$$$ ($$$1 \leq x_i \leq 9$$$), and $$$3$$$ integers $$$l_i$$$, $$$r_i$$$, and $$$c_i$$$. Then he'll write an integer $$$\overline{x_i x_i x_i \cdots x_i}$$$ (there are $$$c_i + k$$$ digits) on a paper strip, and throw it into the $$$(l_i + k - 1)$$$-th box, for each $$$k \in \{1, 2, \cdots, r_i - l_i + 1\}$$$.

But Master qkoqhh loves gambling so he would do another kind of operation. He chooses two integers $$$l_i$$$, $$$r_i$$$, and randomly picks up one paper strip in a box between the $$$l_i$$$-th one and the $$$r_i$$$-th one. Each paper strip has same probability to be chosen. Now an Orz Panda wants to know the expectation of the integer on the paper strip picked up by qkoqhh.

To avoid floating-point errors, you should output the answer modulo $$$M = 1000000007$$$. If the expectation is $$$u/d$$$, you should output $$$(u \cdot d^{-1}) \mod M$$$.

There are multiple test cases. Please process until EOF.

For each test case, the first line contains two integers $$$n$$$ and $$$m$$$. Each of the next $$$m$$$ lines may be:

• 1 $$$l_i$$$ $$$r_i$$$ $$$x_i$$$ $$$c_i$$$: representing an operation by wang9897.
• 2 $$$l_i$$$ $$$r_i$$$: representing an operation by qkoqhh.

It's guaranteed that $$$1 \leq l_i \leq r_i \leq n \leq 10^4$$$, $$$1 \leq m \leq 10^5$$$, and $$$0 \leq c_i \leq 10^9$$$.

For each operation by qkoqhh, output the expectation modulo $$$1000000007$$$. If there is no paper strips which can be chosen, output $$$0$$$.

3 3
1 2 3 5 1
1 1 2 1 3
2 2 3

3907

For the sample, qkoqhh may pick up $$$55, 555$$$, and $$$11111$$$. So the expectation is $$$(55+555+11111)/3 = 3907$$$.