問題一覧 > 通常問題

No.310 Two-Letter Shiritori

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 12
作問者 : anta
お気に入りにしたユーザー ProblemId : 874 / 自分の提出
問題文最終更新日: 2026-06-25 13:17:21
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2015 (順位表) の他の問題:

Problem Statement

In this world there are $N$ kinds of letters, represented by the integers from $1$ to $N$. A two-letter word whose first letter is $a$ and whose second letter is $b$ is represented as the pair of letters $(a,b)$. This world is rich in words: every word except for $M$ non-existent words is listed in the dictionary. That is, $N^2 - M$ words are listed in the dictionary.

You decide to play a special variant of shiritori called "two-letter shiritori". This shiritori is played by one person. One game of two-letter shiritori proceeds as follows.

  1. First, choose one word from the dictionary.
  2. Among the words in the dictionary not yet chosen in this game, choose one whose first letter matches the second letter of the most recently chosen word. That is, if the last chosen word is $(a,b)$ and the newly chosen word is $(c,d)$, then $b = c$ must hold. Repeat choosing words in this way.
  3. The game ends when there are no words left that can be chosen.

A game is called complete if all $N^2 - M$ words in the dictionary are chosen in that one game.

How many complete games are there? Find the count modulo $1000000007$. Here, two games are considered different if the order in which the words are chosen differs.

Input

$N\ M$
$A_1\ B_1$
$\quad\vdots$
$A_M\ B_M$

The first line contains the integer $N$, the number of kinds of letters, and the integer $M$, the number of non-existent words, separated by a space.
The following $M$ lines give the list of non-existent words. For each $i$ ($1 \le i \le M$), $1 \le A_i, B_i \le N$, and this indicates that the word $(A_i,B_i)$ does not exist.

  • $1 \le N \le 4000$
  • $0 \le M \le 4000$
  • The non-existent words are pairwise distinct. That is, if $i \neq j$ then $(A_i,B_i) \neq (A_j,B_j)$.

Output

Output on one line the number of complete games, modulo $1000000007$.

Sample

Sample 1
Input
2 1
1 2
Output
1

The words listed in the dictionary are the three words $(1,1), (2,2), (2,1)$. To choose all three of these words, they must be chosen in the order $(2,2), (2,1), (1,1)$. Therefore, the answer is 1.

Sample 2
Input
2 0
Output
4

For each choice of the first word there is exactly 1 way, for a total of 4 ways.

Sample 3
Input
2 4
2 2
1 2
1 1
2 1
Output
1

The empty game is also counted.

Sample 4
Input
3 3
1 3
3 1
3 2
Output
2
Sample 5
Input
3 0
Output
216
Sample 6
Input
10 0
Output
276247125

Note that you must output the value modulo $1000000007$.

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