仕事の順序 C編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
ポスト
下記の問題をプログラミングしてみよう！
ぱいじょ株式会社で働いている京子ちゃんは、 N 個の仕事を抱えています。 i 番目の仕事を仕事 i と呼びます。
仕事には k 個の順序関係があり、仕事 J_i に取り組むと、仕事 W_i に取り組むことができます。
「仕事 N に取り組むために取り組む必要のある仕事」の順序は何通りありますか？
それぞれの仕事は適切な順序で必ず取り組むことができ、すべての仕事に取り組む必要はありません。
答えは非常に大きくなることがあるので、 1,000,000,007 で割ったあまりを出力してください。
取り組む仕事の順序 A と B が異なるとは、A で取り組む仕事を順に X_1, X_2, ... X_N とし、B で取り組む仕事を順に Y_1, Y_2, ... Y_Mとしたときに、N ≠ M または X_i ≠ Y_i となる i が存在すことをいいます。
入力例1では、「仕事 6 に取り組むために取り組む必要のある仕事」の順序は、以下のように 3 通りとなります。
1 2 6
1 4 6
1 3 5 6
- 入力される値
-
N k
J_1 W_1
J_2 W_2
...
J_k W_k
・ 1 行目に、仕事の総数 N と仕事の順序関係の個数 k が与えられます。
・ 2 行目から k + 1 行目にかけて、 J_i と W_i が与えられます。仕事 J_i に取り組むと、仕事 W_i に取り組むことができます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
「仕事 N に取り組むために取り組む必要のある仕事」の順序が何通りあるか出力してください。
答えは非常に大きくなることがあるので、 1,000,000,007 で割ったあまりを出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 2 ≦ N ≦ 10,000
・ N - 1 ≦ k ≦ Min(N * (N - 1 ) / 2, 100,000 )
・ 1 ≦ J_i < W_i ≦ N
・ J_i ≠ W_i
・ J_i = J_j かつ W_i = W_j となる i, j の組み合わせは存在しない
・ それぞれの仕事は適切な順序で必ず取り組むことができる
- 入力例1
-
6 7
1 2
2 6
1 4
4 6
1 3
3 5
5 6
- 出力例1
-
3
- 入力例2
-
6 7
1 2
1 3
2 4
3 4
3 5
4 6
5 6
- 出力例2
-
3
- 入力例3
-
4 5
1 2
1 3
2 3
2 4
3 4
- 出力例3
-
3
