Happy valentine day! In this problem you'll play adventure game, where you should bring chocolate to your home on 1D virtual world. You start from location 0 and your home located on h. You will take the journey from 0 to h but in the middle of your way to home there could be some bad person who want to steal your chocolate, so you will war with them, if you win, you'll continue the journey, else you'll restart the game. There also some flag, if you successfully take the flag, when you restart the game you'll continue at that flag location but you lose that flag and try to take that flag again, if you take multiple flag, the latest flag that you take will be used and the other flag that you successfully take will be keep.

Now given the map that contain all flag location + probability that you'll successfully take that flag, all war location + probability that you'll win the war, and your home location. Calculate the expected time needed to finish the game. Assume your move speed is constant: 1 unit per time and you do the war and take the flag in no time.

Input

There are multiple test case in one file,

For each test case:

- First line there are two integers h and q denoting the home location and number of object between 0 and h.

- Next q lines there are one character and 3 integers, c, n, a, b:

• c is denoting the type of object ('X' means war, and 'F' means flag)
• n is denoting the location of object, it's guaranteed that n will be strictly increasing (larger than previous n)
• a and b denoting numerator and denominator the probability, so the probability is a/b.

The last line in input file there are two zeros, indicating end of sequence of cases, and your program should terminate.

Output

For each test case output the expected time needed to finish the game. Since the answer could be very large, output it modulo 10⁹+7. All cases is designed such that it's guaranteed the expected time will be an integer.

Constraints

0 < h ≤ 10¹⁸

0 ≤ q ≤ 10⁴

0 < n < h

0 < b < 10⁹+7

0 < a ≤ b

Input File Size < 500 KB

Example

Input:
32 0
32 1
X 16 1 2
32 2
F 8 1 1
X 16 1 2
32 2
F 8 1 2
X 16 1 2
0 0

Output:
32
48
40
44

See also: Another problem added by Tjandra Satria Gunawan