Lovers

The Fool comes to a cross-road, filled with energy, confidence and purpose, knowing exactly where he wants to go and what he wants to do. But he comes to a dead stop. A flowering tree marks the path he wants to take, the one he’s been planning on taking. But standing before a fruit tree marking the other path is a woman. The Fool has met and had relationships with women before, some far more beautiful and alluring. But she is different. Seeing her, he feels as though he’s just been shot in the heart with cupid’s arrow.

There are $n$ empty strings:
$s_1$, $s_2$, . . . , $s_n$.
You are required to perform two kinds of operations:

wrap $l$ $r$ $d$: change $s_i$ to $dsid$ for all l ≤ i ≤ r, where d is a digit character.

query $l$ $r$: query $\sum\limits_{i=l}^{r}$ value($s_i$) (mod $10^9$ + 7), where $value(s)$ is the number that string $s$ represents.

Note that the value of an empty string is 0.

The first line contains one integer $T$, which denote the number of cases.
For each case, the first line contains two integer $n$ and $m$ where $n$ is the number of strings and $m$ is the number of operations.
Each line of the following m lines contains an operation with format
$wrap$ $l$ $r$ $d$
or
$query$ $l$ $r$.

For each case, you should output "Case $i$:"in a line, where $i$ is the case number starting from 1.
Then for each query operation in that case, output a line that contains a single integer that representing the answer for that query operation.

2
3 2
wrap 1 3 1
query 1 2
4 4
wrap 1 3 0
wrap 2 4 3
query 1 4
query 2 3

Case 1:
22
Case 2:
6039
6006

642ccpc吉林

1 ≤ T ≤ 5, 1 ≤ n, m ≤ 1e5, 1 ≤ l ≤ r ≤ n.