yukicoder-310

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
    display: block;
    padding: 9.5px;
    margin: 0 0 10px;
    font-size: 13px;
    line-height: 1.42857143;
    color: #333;
    word-break: break-all;
    word-wrap: break-word;
    background-color: #f5f5f5;
    border: 1px solid #ccc;
    border-radius: 4px;
}
</style>
}}}
== [https://yukicoder.me/problems/no/310 No.310 2文字しりとり] ==

=== Description ===

{{{
#!html
<p>这个世界上有$N$种字符，用$1$到$N$的整数表示。一个长度为$2$的单词可以用一对字符$(a,b)$表示，第一个字符是$a$，第二个字符是$b$。有一个字典，除了$M$个单词，其他$N^2-M$个单词都在里面。</p>

<p>现在开始玩一个游戏，一开始先从字典中拿出一个单词。然后每次要从字典中取出一个之前没有取过的单词，并且要求当前取出来的单词的第一个字符和上一次的第二个字符一样。也就是说如果上次取出来的是$(a,b)$，这次取出来的是$(c,d)$，那么$b=c$。当你再也不能取出单词的时候，游戏结束</p>

<p>如果你拿到了所有$N^2-M$个单词，那么你算通关了这个游戏。问有多少取单词的方案能使你通关这个游戏，方案数$\bmod (10^9+7)$。两种方案不同当且仅当取出单词的顺序不同。
}}}

=== Input ===
{{{
#!html
<p class="input">
$N\ M$ <br/>
$A_1\ B_1$ <br/>
$\quad\vdots$ <br/>
$A_M\ B_M$
</p>

<p>第一行两个整数$N$ ($1 \le N \le 4000$)表示字符种数，$M$ ($0 \le M \le 4000$)表示不存在于字典中的单词个数</p>
<p>接下来$M$行，表示不存在于字典中的单词。第$i$ ($1 \le i \le M$)行有两个整数$A_i$和$B_i$ ($1 \le A_i, B_i \le N$)，表示单词$(A_i,B_i)$不存在。
}}}

=== Output ===

{{{
#!html
输出方案数$\bmod (10^9+7)$。
}}}
=== Sample ===

==== Sample 1 ====
输入
{{{
#!html
<pre>
2 1
1 2
</pre>
}}}
输出
{{{
#!html
<pre>
1
</pre>
}}}

==== Sample 2 ====
输入
{{{
#!html
<pre>
2 0
</pre>
}}}
输出
{{{
#!html
<pre>
4
</pre>
}}}


==== Sample 3 ====
输入
{{{
#!html
<pre>
2 4
2 2
1 2
1 1
2 1
</pre>
}}}
输出
{{{
#!html
<pre>
1
</pre>
}}}

==== Sample 4 ====
输入
{{{
#!html
<pre>
3 3
1 3
3 1
3 2
</pre>
}}}
输出
{{{
#!html
<pre>
2
</pre>
}}}

==== Sample 5 ====
输入
{{{
#!html
<pre>
3 0
</pre>
}}}
输出
{{{
#!html
<pre>
216
</pre>
}}}

==== Sample 6 ====
输入
{{{
#!html
<pre>
10 0
</pre>
}}}
输出
{{{
#!html
<pre>
276247125
</pre>
}}}

No.310 2文字しりとり

Description

这个世界上有$N$种字符，用$1$到$N$的整数表示。一个长度为$2$的单词可以用一对字符$(a,b)$表示，第一个字符是$a$，第二个字符是$b$。有一个字典，除了$M$个单词，其他$N^2-M$个单词都在里面。

现在开始玩一个游戏，一开始先从字典中拿出一个单词。然后每次要从字典中取出一个之前没有取过的单词，并且要求当前取出来的单词的第一个字符和上一次的第二个字符一样。也就是说如果上次取出来的是$(a,b)$，这次取出来的是$(c,d)$，那么$b=c$。当你再也不能取出单词的时候，游戏结束

如果你拿到了所有$N^2-M$个单词，那么你算通关了这个游戏。问有多少取单词的方案能使你通关这个游戏，方案数$\bmod (10^9+7)$。两种方案不同当且仅当取出单词的顺序不同。

Input

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

第一行两个整数$N$ ($1 \le N \le 4000$)表示字符种数，$M$ ($0 \le M \le 4000$)表示不存在于字典中的单词个数

接下来$M$行，表示不存在于字典中的单词。第$i$ ($1 \le i \le M$)行有两个整数$A_i$和$B_i$ ($1 \le A_i, B_i \le N$)，表示单词$(A_i,B_i)$不存在。

Output

输出方案数$\bmod (10^9+7)$。

Sample

Sample 1

输入

2 11 2

输出

Sample 2

输入

2 0

输出

Sample 3

输入

2 42 21 21 12 1

输出

Sample 4

输入

3 31 33 13 2

输出

Sample 5

输入

3 0

输出

Sample 6

输入

10 0

输出

276247125