20251번 - Homework 다국어

문제

There are n children (numbered from 1 to n) learning the arithmetic operations, which include addition “+”, subtraction “−”, multiplication “×”, and division “÷” on rational numbers.

In the beginning, each child has a paper sheet with only a zero on it. Their teacher, Frank, will then give them q operations. The i-th operation consists of an operator c_i and an integer x_i. The children numbered l_i, l_i + 1, . . . , r_i have to append the operator c_i and the integer x_i to their paper sheets. After that, every child has an expression on their sheet to be evaluated.

For example, suppose that n = 3, q = 2, c₁ is “+”, x₁ = 1, l₁ = 1, r₁ = 2, c₂ is “−”, x₂ = 2, l₂ = 2, and r₂ = 3. The expressions on the sheets are are 0 + 1, 0 + 1 − 2 and 0 − 2 for children 1, 2 and 3, respectively.

Since Frank is really lazy and wants to verify the answers quickly, he asks you to calculate the sums of the values of all children’s expressions. Suppose that the value of the expression assigned to child i is a_i/b_i, then the value will be a × b⁻¹ mod 10⁹ + 7 instead, where b⁻¹ denotes the integer satisfying b × b⁻¹ ≡ 1 mod 10⁹ + 7. If the sum is not in [0, 10⁹ + 7), then the sum modulo 10⁹ + 7 should be returned to Frank.

Note: The arithmetic operations has PEMDAS rule, that is, multiplications and divisions should be evaluated before evaluating additions and subtraction.

입력

The first line consists of two space-separated integers n and q. The i-th of the following q lines consists of four space-separated tokens l_i, r_i, c_i, x_i. For the sake of convenience, * and / are used to represent the multiplication and the division operators, respectively.

출력

Output the number that you should return to Frank.

제한

• 1 ≤ n ≤ 10⁵
• 1 ≤ q ≤ 10⁵
• l_i, r_i ∈ [1, n] for all 1 ≤ i ≤ q.
• c_i ∈ {+, -, *, /} for all 1 ≤ i ≤ q. For all 1 ≤ i ≤ q, x_i = 0 implies that c_i is not /.
• x_i ∈ [0, 10⁹ + 7) for all 1 ≤ i ≤ q.

힌트