숙제

1번부터 n번까지 번호가 붙은 n명의 아이들이 유리수의 사칙연산, 즉 덧셈 “+”, 뺄셈 “−”, 곱셈 “×”, 나눗셈 “÷”을 배우고 있다.

처음에 각 아이의 종이에는 0만 적혀 있다. 선생님 Frank는 아이들에게 q개의 연산을 준다. i번째 연산은 연산자 ci와 정수 xi로 이루어진다. ℓi, ℓi + 1, ..., ri번 아이는 자신의 종이에 연산자 ci와 정수 xi를 덧붙여야 한다. 그 뒤 각 아이의 종이에는 계산할 수 있는 식이 하나씩 적혀 있게 된다.

예를 들어 n = 3, q = 2이고 c1이 “+”, x1 = 1, ℓ1 = 1, r1 = 2, c2가 “−”, x2 = 2, ℓ2 = 2, r2 = 3이라고 하자. 그러면 1, 2, 3번 아이의 종이에 적힌 식은 각각 0 + 1, 0 + 1 − 2, 0 − 2이다.

Frank는 몹시 게으르고 답을 빨리 확인하고 싶어 하므로, 모든 아이의 식의 값의 합을 계산해 달라고 부탁한다. i번 아이에게 주어진 식의 값을 ai/bi라고 하면, 그 값 대신 a × b−1 mod 109 + 7을 사용한다. 여기서 b−1은 b × b−1 ≡ 1 mod 109 + 7을 만족하는 정수이다. 합이 [0, 109 + 7)에 들어가지 않으면, 합을 109 + 7로 나눈 나머지를 Frank에게 알려 주어야 한다.

참고: 사칙연산에는 PEMDAS 규칙이 적용된다. 즉, 덧셈과 뺄셈보다 곱셈과 나눗셈을 먼저 계산한다.

첫째 줄에 공백으로 구분된 두 정수 n과 q가 주어진다. 이어지는 q개 줄 중 i번째 줄에는 공백으로 구분된 네 개의 토큰 ℓi, ri, ci, xi가 주어진다. 편의상 곱셈과 나눗셈 연산자는 각각 *와 /로 나타낸다.

Frank에게 알려 주어야 하는 수를 출력한다.

• 1 ≤ n ≤ 105
• 1 ≤ q ≤ 105
• 모든 1 ≤ i ≤ q에 대해 ℓi, ri ∈ [1, n].
• 모든 1 ≤ i ≤ q에 대해 ci ∈ {+, -, *, /}. 모든 1 ≤ i ≤ q에 대해 xi = 0이면 ci는 /가 아니다.
• 모든 1 ≤ i ≤ q에 대해 xi ∈ [0, 109 + 7).