問題一覧 > 通常問題

No.1222 -101

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 54
作問者 : anagohirameanagohirame / テスター : satashunsatashun
7 ProblemId : 3252 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-08-31 02:38:52

問題文

長さ N の整数列 (A1,A2,,AN) であり,以下の条件を満たすものの個数を 109+7 で割った余りを求めてください。

  • 1Ai1 (1iN)
  • i=LjRjAi(=ALj××ARj)=Pj (1jM)

入力

N M
L1 R1 P1
L2 R2 P2

LM RM PM

  • 入力はすべて整数
  • 1N2×105
  • 0MN
  • 1LiRiN
  • 1Pi1
  • ijRiRj

出力

答えを1行に出力してください。

サンプル

サンプル1
入力
3 2
1 2 -1
2 3 0
出力
2

1Ai1 (1i3) のほかに, A1×A2=1, A2×A3=0 の2条件があります。 これらを全て満たす数列 (A1,A2,A3)(1,1,0), (1,1,0) の2つです。

サンプル2
入力
4 3
1 2 1
2 3 0
3 4 -1
出力
0

条件を満たす数列は存在しません。

サンプル3
入力
100 0
出力
886041711

積についての条件がないので,A1A100 のいずれも 1, 0, 1 の3つから自由に選べます。よって条件を満たす数列は 3100 通りです。
109+7 で割った余りを出力することに注意してください。

サンプル4
入力
10 7
1 4 -1
2 5 0
8 8 -1
1 6 0
8 10 -1
6 9 1
1 7 0
出力
32

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