seuOJ294 - 御坂妹妹

题目描述

御坂美琴和妹妹在御坂网络网络上玩起了游戏。

御坂妹妹：“规则应该由妹妹来定，姐姐让妹妹需要什么理由吗，御坂试着摆出妹妹的样子。”

御坂美琴：“真拿你没办法。”

御坂妹妹：“御坂网络是一个有向无环图，每个点会被染成黑或者白色，每个点上可能有很多硬币。姐姐每次可以选择一个有硬币的黑点 xx，然后选择一条从 xx 出发的边 (x,y)(x, y) 把一个硬币送到 yy，御坂每次可以选择一个有硬币的白点 uu，然后选择一条从 uu 出发的边 (u,v)(u, v) 把一个硬币送到 vv 点，姐姐和御坂轮流操作，如果谁不能进行操作了谁就输了，初始的时候每个点都可能有一个硬币，或者没有硬币。作为姐姐，当然应该让妹妹先行，姐姐让妹妹需要什么理由吗。御坂试着摆出妹妹的样子并解释道。”

御坂美琴知道妹妹拥有强大的计算网络，可以很快算出所有初始局面的胜负，现在御坂美琴想请你帮忙，在所有 2n2^n 种初始局面中，有多少种是妹妹能够获胜的，请输出答案除 109+710^9 + 7 后的余数即可。

输入格式

第一行输入两个整数 n,m(1≤n≤300，0≤m≤n(n−1)2)n, m(1 \leq n \leq 300， 0 \leq m \leq \frac{n(n - 1)}{2})，表示御坂网络的大小和御坂网络的边数。

第二行输入一个长度为 nn 的字符串，字符串第 ii 位为 'B' 表示该点是黑点，字符串第 ii 位为 'W' 表示该点是白点。

接下来 mm 行，每行两个整数 (x,y)(1≤x,y≤n)(x, y)(1 \leq x, y \leq n), 表示有一条从 xx 到 yy 的有向边。

输出格式

输出一行一个整数表示妹妹能获胜的初始局面总数除 109+710^9 + 7 后的余数即可。

样例

样例输入

5 4
WWWWW
1 2
2 3
3 4
4 5

样例输出

30