仕事の順序 R(Beta)編（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 が存在する場合

また、それぞれの仕事は適切な順序で必ず取り掛かることができ、すべての仕事に取り組む必要はありません。

入力される値

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

問題一覧へ戻る