题目描述

XB 家附近有 个十字路口，共由 条单行道相连。 XB 家住在编号为 的十字路口附近，所以他会从 出发。每条路上都恰好有一家店铺出售这 种原料中的 种或多种。 XB 喜欢货比三家，所以就算他已经买来了某家店铺出售的所有原料，他还是会走进这家店铺看看。如果 XB 没有进入一条路上的店铺的话，他只需要 分钟时间通过这条路，否则他需要多花 分钟时间逛店 铺。 下面是 的情况： 那么 XB 在 分钟内的行走路线为以下 种： XB 想知道，在他的朋友来之前，也就是 分钟的时间内，他有多少种不同的行走路线，满足从 出 发，购买到所有 种原料后再返回 。可以到达 之后，再出去，只要时间够。

输入格式（文件名：palacinke.in）

第一行包括两个正整数 ，表示十字路口的数量以及单行道的数量。 接下来 行包括两个不同的正整数 和 ，以及一个字符串 ，分别用空格隔开。表示有一条 到 的单行道，并且这条路上的店铺出售的原料为 。 会包含 到 个字符， B 代表面粉， J 代表鸡 蛋， M 代表牛奶， P 代表奶油。不含重边和自环。 最后一行包括一个正整数 ，表示 XB 朋友在 分钟之后来。

输出格式（文件名：palacinke.out）

输出仅一行，包括一个正整数，表示满足要求的路线数量。数据较大，规定对 取模