题目描述

本题使用石头剪刀布规则：石头 R 胜剪刀 S，剪刀 S 胜布 P，布 P 胜石头 R；相同则平局。

有 $n$ 个机器人。每个机器人有一个长度为 $k$ 的固定策略串以及一个非负整数状态 state。机器人每进行一局游戏时：

1. 选择 strategy[state mod k] 作为本局动作；
2. 将 state 加一。

两个机器人之间的一场比赛恰好进行 $k$ 局。比赛结果记为二元组 (A,B)，分别表示两台机器人获胜的局数。

如果无论两台机器人比赛开始时各自的 state 是多少，比赛结果都完全相同，则称这两台机器人是默契的。

一个非空机器人子集是默契子集，当且仅当其中任意两台机器人都互相默契。单个机器人构成的子集自然合法。

求默契子集数量，对 $10^9+7$ 取模。

只直接给出前 $q$ 台机器人的策略，其余机器人的策略由伪随机生成器产生。设 now = seed，执行：

a = 22222223
b = 12345678
mod = 1000000007

对于 i = q, q+1, ..., n-1：
    strategy[i] = ""
    重复 k 次：
        t = now mod (pR + pP + pS)
        若 t < pR：追加 'R'
        否则若 t < pR + pP：追加 'P'
        否则：追加 'S'
        now = (now * a + b) mod mod

其中 $k$ 等于任意一个已给策略串的长度。

输入格式

第一行输入六个整数 $n,q,seed,pR,pP,pS$。

接下来 $q$ 行，每行输入一个长度为 $k$ 的字符串，依次表示前 $q$ 台机器人的策略。

输出格式

输出默契子集数量对 $10^9+7$ 取模的结果。

数据范围

• $1\le n\le 100000$；
• $1\le k\le 18$；
• $1\le q\le\min(n,1000)$；
• 每个给定策略串只包含 R、P、S；
• $0\le seed\le 10^9+6$；
• $0\le pR,pP,pS\le 1000$；
• $pR+pP+pS>0$。

样例

输入

3 3 0 1 1 1
RRR
RPS
RPS

输出

5