TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Description

殿壬是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲,而現在要講的,是殿壬八歲大時的故事。

再講這個故事之前,需要先介紹一下殿壬所居住個國家(以下簡稱電人國):

電人國有一個捷運站,站內只有兩種列車:往東以及往西。這個捷運站一天共營運 $N$ 分鐘,且每一分鐘皆洽有一班車進站。
有 $M$ 個旅客,第 $i$ 個旅客在時間點 $t_i$ 抵達捷運站,且他想要乘坐往方向 $d_i$ 的列車(若在時間 $t_i$ 的列車恰是往方向 $d_i$ ,那他可以直接搭乘)。每位旅客各有各的時間規劃,因此有些人可以接受等很久才做到列車,而有些人則希望越快坐上列車越好。
正式的說,我們可以用容忍值 $c_i$ 來量化第 $i$ 個乘客對於列車等待時間的容忍程度,一旦這位乘客等待超過 $c_i$ 分鐘,他便會向主管機關投訴。

由於殿壬是天才兒童,因此他八歲時就受聘幫忙安排捷運班表。由於這個國家的人生活得非常規律,因此捷運公司已經知道隔天會有哪些乘客、在哪個時間點來到捷運站,並要坐往哪個方向的列車。
捷運公司最怕的便是收到投訴,因此殿壬安排的捷運班次表必須讓所有人的等待時間都不超過他的容忍度。
除此之外,由於一些政策的規定,某些時間點的列車已經被政府決定了。
殿壬怕自己做的決定長官感到不滿意,因此他決定列下所有可能的捷運班次表,再交由長官自行選擇。但是可能的安排方式實在太多了,因此請你幫他算出總共有幾種可能的捷運班次表。

Input Format

輸入的第一行有兩個正整數 $N, M$ ,代表列車的班數以及乘客的數量。
接著一行有一個長度為 $N$ ,由 EW? 所組成的字串 $S$ ,代表捷運班表。
若第 $i$ 個字元為 E ,代表第 $i$ 分鐘已經由政府安排一台往東的列車。
若第 $i$ 個字元為 W ,代表第 $i$ 分鐘已經由政府安排一台往西的列車。
若第 $i$ 個字元為 ? ,代表殿壬可以自由決定第 $i$ 分鐘的列車方向。
接著 $M$ 行,每行有一個整數 $t_i$ 、一個字元 $d_i$ 以及一個整數 $c_i$ ,分別代表第 $i$ 個乘客的資訊(若字元為 E 代表他搭乘往東的列車,若為 W 則代表他要搭乘往西的列車)。

  • $1 \leq N \leq 3000$
  • $0 \leq M \leq 3000$
  • $0 \leq c_i \leq N - t_i$
  • $1 \leq t_i \leq N$

Output Format

輸出一個整數代表可能的捷運班表的數量。由於答案可能很大,請輸出其除以 $10^ 9 + 7$ 的餘數。

Sample Input

Sample Input 1:
2 0
W?

Sample Input 2:
2 1
W?
2 W 0

Sample Output

Sample Output 1:
2

Sample Output 2:
1

Hints

範例測試資料一中, WWWE 皆符合條件。
範例測試資料二中, WE 不符合條件因為第一位乘客只能忍受等待 0 分鐘。

Problem Source

Subtasks

No. Testdata Range Score
1 0~29 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1
1 1000 262144 262144 1
2 1000 262144 262144 1
3 1000 262144 262144 1
4 1000 262144 262144 1
5 1000 262144 262144 1
6 1000 262144 262144 1
7 1000 262144 262144 1
8 1000 262144 262144 1
9 1000 262144 262144 1
10 1000 262144 262144 1
11 1000 262144 262144 1
12 1000 262144 262144 1
13 1000 262144 262144 1
14 1000 262144 262144 1
15 1000 262144 262144 1
16 1000 262144 262144 1
17 1000 262144 262144 1
18 1000 262144 262144 1
19 1000 262144 262144 1
20 1000 262144 262144 1
21 1000 262144 262144 1
22 1000 262144 262144 1
23 1000 262144 262144 1
24 1000 262144 262144 1
25 1000 262144 262144 1
26 1000 262144 262144 1
27 1000 262144 262144 1
28 1000 262144 262144 1
29 1000 262144 262144 1