VAL_GAM4 - Happy Valentine Day (Valentine Adventure Game)

no tags 

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.

Illustration

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 109+7. All cases is designed such that it's guaranteed the expected time will be an integer.

Constraints

0 < h ≤ 1018

0 ≤ q ≤ 104

0 < n < h

0 < b < 109+7

0 < ab

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


hide comments
suhash: 2020-08-29 15:33:15

Thanks for the problem, Tjandra! Really enjoyed solving this one. :)

(Tjandra Satria Gunawan)(曾毅昆): 2014-02-28 17:34:55

@Vishvajeet Singh Rathore: I don't want to spoil the logic, but It's guaranteed that the answer is always an integer, you need to output that number modulo 1000000007.

Vishvajeet Singh Rathore: 2014-02-26 22:12:02

probability of winning and loosing is given by user. but how to use that. means either we can loose the war or flag or win it that gives us probability as 1/2. what if user input probability as 2/3 or any other. how to handle that... plz help

Mitch Schwartz: 2014-02-17 06:56:18

If you lose war when you have two flags, you keep the first flag and only lose the most recent one, right? Or do you lose both flags?

Another question: n<h is guaranteed, right?


Ans: Yes, only lose the most recent flag, and it's guaranteed that n<h


(Mitch) Thanks!

Last edit: 2014-02-18 00:22:24

Added by:Tjandra Satria Gunawan
Date:2014-02-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem