No.762 PDCAパス

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 通常問題
タグ : / 解いたユーザー数 87
作問者 : maimai / テスター : matsu7874matsu7874
3 ProblemId : 1986 / 出題時の順位表

問題文

$N$個の頂点と$M$個の無向辺から構成されるグラフが与えられます.

$i$番目の頂点には,P,D,C,Aのいずれかの文字が書き込まれています.
$j$番目の辺は,$u_j$番目の頂点と,$v_j$番目の頂点に接続しています.


始点と終点が異なり,どの頂点も高々一度しか通らない,ある頂点からある頂点への行き方をパスと呼びます.
長さ3のパスとは,3つの辺と4つの頂点によって構成されているパスのことです.

長さ3のパスについて,端から端へ頂点を辿るとPDCAと読むことができる時,PDCAパスと呼ぶことにします.


グラフを構成する長さ3のパスの中で,PDCAパスは幾つ存在するでしょうか?$10^9+7$で割った余りを求めてください.

入力

N M
S
u_1 v_1
...
u_M v_M

$2 \le N \le 10^5$
$0 \le M \le 10^5$
$|S| = N$
$1 \le u_i \lt v_i \le N$
多重辺・自己ループ辺が存在するグラフは与えられない.
文字列 $S$ を構成する文字はP,D,C,Aのいずれかである
$S$ の $i$ 文字目は,頂点番号 $i$ にその文字が書き込まれていることを示す.

出力

PDCAパスの個数を1000000007で割った余りを出力してください.

最後に改行してください。

サンプル

サンプル1
入力
7 11
PAAPCDD
1 3
1 5
1 6
2 5
2 6
3 5
5 6
4 5
5 7
4 7
2 7
出力
4

1,6,5,21,6,5,34,7,5,24,7,5,3 の4通りがあります.

サンプル2
入力
6 3
ACPPPD
1 2
3 4
4 5
出力
0

グラフは連結とは限りませんし,PDCAパスが存在しないかもしれません.

サンプル3
入力
11 11
AAACCCDDPPP
1 4
1 5
2 5
4 7
5 7
7 9
7 10
2 4
3 6
6 8
8 11
出力
9

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。