問題一覧 > 通常問題

No.762 PDCAパス

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 159
作問者 : maimai / テスター : matsu7874matsu7874
3 ProblemId : 1986 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-11-28 09:48:59

問題文

$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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。