002 - 天空の雲渡り

ストーリー

とある島にナウ人間という特殊な人間がいた。

彼は神なるナウマンゾウ(個人的な意見です)に出会うために冒険をしていた。

雨や風に打ちひしがれ、「諦めたい」という気持ちが強まり、山の頂上で途方に暮れていた。

すると！

普段よりも不透明な不思議な雲が近くに散らばっていることに気付いた。

これは何だろう…ふと触ってみる。「これは乗れる！」

その時気づいてしまった。

その先にその試練を乗り越えよといわんばかりに『ナウマンゾウ』がいたのだ。

「いかなければならない」「越えられない試練はない」

そう言い聞かせ、彼は旅立っていった。

当然ジャンプしないと行けないような雲もある。

自分の乗っている雲に塩酸をかけると、雲は固まりジャンプができるという言い伝えがあったことを思い出した。

実験したところ、100ml程度で十分なようだ。

雲から雲へ渡るとき、どちらかの方向に地面と平行に強い風が吹き、一方通行でしか渡れないようだ。

さらに同じところへ戻ってくる手立てもなくなる。見積もることの大切さが目に染みた。

まずは行ける方法はどのくらいあるのか見積もることにした。

問題

雲の数、雲から雲へ風の吹いている所の数、所持している塩酸の量が与えられ、
また、スタートする雲とナウマンゾウのいる雲が与えられる。

また、a_iの雲からb_iの雲へ風が吹いていて、
ジャンプしないといけないかを問う c_i ( 1 ≦ i ≦ M )が与えられるので、

スタートする雲sから、ナウマンゾウのいる雲gまで行くための通りは何通りあるのか出力せよ!
そのような通りはたくさんあることが予測されるため、10⁹ + 7で割った余りを出力せよ。

この問題でできる経路には閉路が存在しない、また、一方通行であることが保証される。

塩酸は、一回ジャンプするごとに、100[ml]だけ消費されることが保証される。

入力形式

一行目にN, M, Hが与えられる。
これは、雲の数、　雲から雲へ風が吹いているところの数、　塩酸の量[ml]である。

二行目には、s, gが与えられる。
これは、スタート地点の雲、　ナウマンゾウがいるゴール地点の雲である。

3 ~ 2 + M 行目まで、 a_i , b_i , c_i が与えられる。
これらは、a_iの雲からb_iの雲へ風が吹いていることを示し、

c_i = 1　の時、 ジャンプしないと、b_i へは行けず、
c_i = 0　の時、 ジャンプをせずに、b_i へ行けることを示す。

N M H
s g
a1 b1 c1
a2 b2 c2
  .
  .
  .
aM bM cM

出力形式

sからgへ向かうことができる通りを一行に出力せよ。

制約

• 1 ≦ N ≦ 10000
• 1 ≦ M ≦ 100000
• 0 ≦ H ≦ 10000
• 1 ≦ a_i ≦ N
• 1 ≦ b_i ≦ N
• 0 ≦ c_i ≦ 1

実質Mの制約は30000程度までである。

入出力例

入力例1

7 9 0
1 7
1 2 0
1 3 0
3 6 0
3 7 0
2 4 0
2 5 0
5 4 0
6 7 0
4 7 0

出力例1

4

入力例2

13 18 123
3 12
3 1 0
3 2 0
1 8 0
1 10 1
2 6 1
2 4 0
8 7 0
10 7 0
10 5 1
6 9 0
4 9 1
7 12 1
7 5 0
5 12 0
9 13 0
9 11 0
11 13 0
13 12 0

出力例2

7

コメント

天気よければみんなプロ

Mの制約が100000を超えない曖昧な値なため(有向非巡回グラフなため)、そこがわかりづらかった場合は申し訳ないです。

何かご意見が有れば、tinumu(ei1629)まで宜しくお願いします。