406021: GYM102219 D Ali The Multi-billionaire

Ali is a multi-billionaire. Sometimes, for fun he give away his money to his friends. But Ali is a strange person, so he likes to play a game first.

First, he arrange all his friends in a circle. He assign his friends number from $$$1$$$ to $$$N$$$ in clockwise direction. Each of his friends need to remember two integer, $$$a$$$ and $$$b$$$ which its initial value is $$$1$$$. These two integer is used to calculate another integer $$$x$$$ using the following formula:

In the game, Ali give several command to his friends. In each command, Ali will specify four thing, the integer to increment (either $$$a$$$ or $$$b$$$), an integer $$$h$$$ which is how much should the number be incremented by and two position, $$$j$$$ and $$$k$$$. When Ali call out the command, his friend from $$$j$$$ to $$$k$$$ in clockwise direction will increment their number by $$$h$$$. After all the commands are given out, all his friend can calculate their $$$x$$$, and that is the amount that Ali will give out to the respective friend.

Given the number of friends $$$N$$$ and $$$M$$$ instructions that Ali give out, find out how much in total Ali need to give to his friends.

The first line starts with two number $$$N$$$ and $$$M$$$, $$$(1 ≤ N, M ≤ 2 × 10^4 )$$$ which is the number of friends and the number of instruction. The next $$$M$$$ line consist of one character and three integer, $$$c_{i} , j_{i} , k_{i}$$$ and $$$h_{i}$$$ $$$(1 ≤ j_{i} , k_{i} ≤ N, 1 ≤ h_{i} ≤ 10^6 )$$$. $$$c_{i}$$$ is either $$$'a'$$$ or $$$'b'$$$.

Print a single integer which is the total $$$x$$$ across all Ali's friend.

7 4
a 6 3 1
a 2 5 4
a 7 1 1
b 7 2 1

16

Note that while each $$$x$$$ is modded by $$$10^5 + 7$$$, the total is not