E 国有 个城市，编号为 至 。为了让城市之间的来往更加便利，E 国的交通部想在 个城市间建造一些虫洞。每条虫洞是一条单向的从某个城市到另一个城市的通道。允许通道的起点和终点是同一个城市，也允许两个城市之间有多个虫洞连接。
为了区分虫洞的建造时间，交通部给每一条虫洞一个正整数的编号。
我们称一种虫洞的建造方案是好的，若它满足如下四个条件：
- 存在一个非负整数 使得每个城市恰好是 条虫洞的起点，也恰好是 条虫洞的终点。
- 对于每个城市而言，在以它为起点的虫洞的编号中， 到 恰好各出现一次。
- 对于每个城市而言，在以它为终点的虫洞的编号中， 到 恰好各出现一次。
- 任意选取一个城市 和正整数 。设从 出发，先经过一次编号为 的虫洞，再经过一次编号为 的虫洞，到达城市 。设从 出发，先经过一次编号为 的虫洞，再经过一次编号为 的虫洞，到达城市 。则条件 必定满足。
特别地，不建造任何虫洞的方案也是好的。
现在，建造师已建造了 条虫洞，且给了它们 的编号，此时这样的建造方案是好的。他想要新建造 条虫洞，并给它们 的编号。他必须保证这 条虫洞形成的建造方案仍然是好的。他想知道有多少种新建造 条虫洞的方法，使得这 条虫洞形成的建造方案是好的。
由于答案很大，你只需要求出方案数除以 的余数。