题目背景

苍梧营地夜间用红黄两色信号旗传递消息。一排 N 个旗位，每个旗位挂一面旗： 红旗记作 R，黄旗记作 Y。

通讯官整理出一条老规矩：整条旗语里不允许出现连续三面黄旗（即不能出现子串 YYY）， 否则会被当成“休战”信号误读。其余任意排列都合法。

现在有 n 个旗位，其中 k 个旗位已经被前任通讯官固定挂了旗（给定这些位置与颜色， 固定信息之间不会互相矛盾），其余旗位由你自由决定颜色。

请计算：满足“不含 YYY”且与固定信息一致的编排方案数，对 1 000 000 007 取模。

题目描述

给定 n、k 和 k 条固定信息 (p_i, c_i)（1 ≤ p_i ≤ n，c_i ∈ {R,Y}，位置互不相同）， 求长度 n、不含连续三个 Y、且在所有固定位置上颜色相符的字符串数量，mod 1e9+7。

输入格式

第一行两个整数 n、k（1 ≤ n ≤ 2000，0 ≤ k ≤ n）。 接下来 k 行，每行一个整数 p_i 和一个字符 c_i（空格分隔）；k=0 时没有后续行。

输出格式

一行一个整数：方案数 mod 1 000 000 007。

样例输入 #1

3 0

样例输出 #1

7

样例输入 #2

4 2
1 Y
4 Y

样例输出 #2

3

样例解释

样例 1：长度 3 共 8 种排列，唯一非法的是 YYY，故 7。

样例 2：模式 Y ? ? Y。枚举中间两位：Y R R Y、Y R Y Y、Y Y R Y 合法； Y Y Y Y 含 YYY 非法。共 3 种。

数据范围

• 1 ≤ n ≤ 2000；0 ≤ k ≤ n；固定位置互不相同。
• k=0 时答案即长度 n、不含连续三个 Y 的二元串数量。