問題一覧 > 通常問題

No.762 PDCAパス

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 163
作問者 : mai / テスター : matsu7874
3 ProblemId : 1986 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-10 00:15:56

問題文

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

ii番目の頂点には,P,D,C,Aのいずれかの文字が書き込まれています.
jj番目の辺は,uju_j番目の頂点と,vjv_j番目の頂点に接続しています.


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

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


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

入力

N M
S
u_1 v_1
...
u_M v_M

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

出力

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もしくは右上の雲マークをクリックしてアカウントを作成してください。