给稻田引水的地块有 n 块，编号从 1 到 n。
地块之间有 m 条水渠。
一条水渠 "a b" 表示水只从第 a 块流向第 b 块。
同样两块之间可能有多条水渠，即使连接的是同样两块，不同的水渠也算作不同的水渠。
从任何地块沿水渠流下去，都不会再回到那块。
往第 1 块（泉眼）倒水后，水会反复从当前地块流出的水渠中选一条流过去，到达没有流出水渠的地块时就积在那里停下。
求水一共有多少种流法。
经过的水渠顺序不同，就算作不同的流法。
如果第 1 块没有流出的水渠，水就原地积在第 1 块，这也算一种流法。
数可能非常大，所以输出除以 1,000,000,007 的余数。
5 6 1 2 1 3 2 4 3 4 4 5 1 5
3
6 6 1 2 1 3 2 4 3 4 3 5 6 2
3
3 0
1
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
设 ways[v] ="水从第 1 块流到 v 的方法数"，对每条流入 v 的水渠，把它出发地块的 ways 加上即可（动态规划）。
答案是所有没有流出水渠的地块（积水的地块）的 ways 之和——第 1 块没有流出的水渠时，第 1 块本身就是这样的地块，ways[1] = 1 直接就是答案（第三个例子）。
但相加之前出发地块的值必须已经算完，所以按拓扑排序的顺序往下流：先取出流入水渠都已算完的地块（Kahn 算法——数出 inflow，变成 0 的地块放进队列）。
陷阱一：队列里只放第 1 块开始的话，从第 1 块到不了的地块（第二个例子的第 6 块）流出的水渠会留在 inflow 里，下面的地块永远取不出来——要把没有流入水渠的地块全部放进去（它们的 ways 是 0，答案不变）。
陷阱二：按编号顺序往下流是错的——没有保证编号小的地块在上面。
陷阱三：把倒水的第 1 块排除在积水地块之外，第三个例子就会得到 0。
陷阱四：流法数会像 2^2500 那样变大。
每加一次就要取余：C、C++ 的 long long 只在最后除一次也会溢出；Python 不会溢出，但不取余就会直接输出巨大的数。
两个余数之和约 20 亿，勉强能放进 32 位 int（约 21 亿），稳妥起见 C、C++ 用 long long，Java、C# 用 long；JavaScript、TypeScript、Craykon 的数精确到 2^53，直接用就行。
陷阱五：用带记忆的递归 count(v) 来数，在 10,000 块的链上 Python 会超过默认递归上限（1,000）出现 RecursionError，Craykon 也会在 4,000 层左右停下——用队列的拓扑排序没有深度问题。
队列各语言不同：Python collections.deque，Java ArrayDeque<Integer>，C# Queue<int>，C++ std::queue<int>，C 用数组加队头、队尾位置，JavaScript、TypeScript、Craykon 只往列表末尾添加并移动队头位置（head）（shift() 每次都要整体前移，很慢）。
Craykon 的列表最多 10,000 个元素，所以把编号减 1 从 0 号开始存（新列表(n, 0)）。
import sysfrom collections import deque MOD = 1_000_000_007data = sys.stdin.read().split()n, m = int(data[0]), int(data[1]) down = [[] for _ in range(n + 1)] # down[a] = a에서 물이 흘러가는 칸들(물길마다 한 번씩)inflow = [0] * (n + 1) # 아직 계산하지 않은, 들어오는 물길의 수for i in range(m): a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i]) down[a].append(b) inflow[b] += 1 # 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 차례로 꺼낸다(1번에서 못 가는 칸도 모두 넣는다)ways = [0] * (n + 1) # ways[v] = 1번에서 v까지 흐르는 방법의 수(MOD로 나눈 나머지)ways[1] = 1ready = deque(v for v in range(1, n + 1) if inflow[v] == 0)while ready: v = ready.popleft() for nxt in down[v]: ways[nxt] = (ways[nxt] + ways[v]) % MOD inflow[nxt] -= 1 if inflow[nxt] == 0: ready.append(nxt) # 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다total = 0for v in range(1, n + 1): if not down[v]: total = (total + ways[v]) % MODprint(total)const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data;const MOD = 1000000007; const down = Array.from({ length: n + 1 }, () => []); // down[a] = a에서 물이 흘러가는 칸들(물길마다 한 번씩)const inflow = new Array(n + 1).fill(0); // 아직 계산하지 않은, 들어오는 물길의 수for (let i = 0; i < m; i++) { const a = data[2 + 2 * i], b = data[3 + 2 * i]; down[a].push(b); inflow[b]++;} // 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다)const ways = new Array(n + 1).fill(0); // ways[v] = 1번에서 v까지 흐르는 방법의 수(MOD로 나눈 나머지)ways[1] = 1;const queue = [];for (let v = 1; v <= n; v++) if (inflow[v] === 0) queue.push(v);for (let head = 0; head < queue.length; head++) { const v = queue[head]; for (const next of down[v]) { ways[next] = (ways[next] + ways[v]) % MOD; // 두 수 모두 MOD보다 작아 합이 2^53보다 훨씬 작다 if (--inflow[next] === 0) queue.push(next); }}// 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다let total = 0;for (let v = 1; v <= n; v++) if (down[v].length === 0) total = (total + ways[v]) % MOD;console.log(total);import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data;const MOD = 1000000007; const down: number[][] = Array.from({ length: n + 1 }, (): number[] => []); // down[a] = a에서 물이 흘러가는 칸들const inflow: number[] = new Array<number>(n + 1).fill(0); // 아직 계산하지 않은, 들어오는 물길의 수for (let i = 0; i < m; i++) { const a = data[2 + 2 * i], b = data[3 + 2 * i]; down[a].push(b); inflow[b]++;} // 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다)const ways: number[] = new Array<number>(n + 1).fill(0); // ways[v] = 1번에서 v까지 흐르는 방법의 수(MOD로 나눈 나머지)ways[1] = 1;const queue: number[] = [];for (let v = 1; v <= n; v++) if (inflow[v] === 0) queue.push(v);for (let head = 0; head < queue.length; head++) { const v = queue[head]; for (const next of down[v]) { ways[next] = (ways[next] + ways[v]) % MOD; // 두 수 모두 MOD보다 작아 합이 2^53보다 훨씬 작다 if (--inflow[next] === 0) queue.push(next); }}// 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다let total = 0;for (let v = 1; v <= n; v++) if (down[v].length === 0) total = (total + ways[v]) % MOD;console.log(total);import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.StringTokenizer; public class Main { static final int MOD = 1_000_000_007; public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); List<List<Integer>> down = new ArrayList<>(); // down.get(a) = a에서 물이 흘러가는 칸들 for (int v = 0; v <= n; v++) down.add(new ArrayList<>()); int[] inflow = new int[n + 1]; // 아직 계산하지 않은, 들어오는 물길의 수 for (int i = 0; i < m; i++) { st = new StringTokenizer(in.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); down.get(a).add(b); inflow[b]++; } // 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다) long[] ways = new long[n + 1]; // 두 나머지의 합은 int를 넘을 수 있어 long ways[1] = 1; ArrayDeque<Integer> ready = new ArrayDeque<>(); for (int v = 1; v <= n; v++) if (inflow[v] == 0) ready.add(v); while (!ready.isEmpty()) { int v = ready.poll(); for (int next : down.get(v)) { ways[next] = (ways[next] + ways[v]) % MOD; if (--inflow[next] == 0) ready.add(next); } } // 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다 long total = 0; for (int v = 1; v <= n; v++) if (down.get(v).isEmpty()) total = (total + ways[v]) % MOD; System.out.println(total); }}using System;using System.Collections.Generic; class Program{ const long MOD = 1_000_000_007; static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(first[0]); int m = int.Parse(first[1]); var down = new List<int>[n + 1]; // down[a] = a에서 물이 흘러가는 칸들(물길마다 한 번씩) for (int v = 0; v <= n; v++) down[v] = new List<int>(); var inflow = new int[n + 1]; // 아직 계산하지 않은, 들어오는 물길의 수 for (int i = 0; i < m; i++) { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int a = int.Parse(p[0]), b = int.Parse(p[1]); down[a].Add(b); inflow[b]++; } // 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다) var ways = new long[n + 1]; // 두 나머지의 합은 int를 넘을 수 있어 long ways[1] = 1; var ready = new Queue<int>(); for (int v = 1; v <= n; v++) if (inflow[v] == 0) ready.Enqueue(v); while (ready.Count > 0) { int v = ready.Dequeue(); foreach (int next in down[v]) { ways[next] = (ways[next] + ways[v]) % MOD; if (--inflow[next] == 0) ready.Enqueue(next); } } // 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다 long total = 0; for (int v = 1; v <= n; v++) if (down[v].Count == 0) total = (total + ways[v]) % MOD; Console.WriteLine(total); }}#include <iostream>#include <queue>#include <vector> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); const long long MOD = 1000000007; int n, m; std::cin >> n >> m; std::vector<std::vector<int>> down(n + 1); // down[a] = a에서 물이 흘러가는 칸들(물길마다 한 번씩) std::vector<int> inflow(n + 1, 0); // 아직 계산하지 않은, 들어오는 물길의 수 for (int i = 0; i < m; i++) { int a, b; std::cin >> a >> b; down[a].push_back(b); inflow[b]++; } // 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다) std::vector<long long> ways(n + 1, 0); // 두 나머지의 합은 int를 넘을 수 있어 long long ways[1] = 1; std::queue<int> ready; for (int v = 1; v <= n; v++) if (inflow[v] == 0) ready.push(v); while (!ready.empty()) { int v = ready.front(); ready.pop(); for (int next : down[v]) { ways[next] = (ways[next] + ways[v]) % MOD; if (--inflow[next] == 0) ready.push(next); } } // 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다 long long total = 0; for (int v = 1; v <= n; v++) if (down[v].empty()) total = (total + ways[v]) % MOD; std::cout << total << "\n";}#include <stdio.h> #define MAXN 10001#define MAXM 10000#define MOD 1000000007LL /* 인접 목록을 배열로: head[a]는 a에서 나가는 첫 물길 칸, next[e]는 다음 칸(-1이면 끝) */static int head[MAXN], next[MAXM], to[MAXM];static int inflow[MAXN]; /* 아직 계산하지 않은, 들어오는 물길의 수 */static long long ways[MAXN]; /* 두 나머지의 합은 int를 넘을 수 있어 long long */static int queue[MAXN]; int main(void) { int n, m; scanf("%d %d", &n, &m); for (int v = 1; v <= n; v++) head[v] = -1; for (int e = 0; e < m; e++) { int a, b; scanf("%d %d", &a, &b); to[e] = b; next[e] = head[a]; head[a] = e; inflow[b]++; } /* 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다) */ ways[1] = 1; int qh = 0, qt = 0; for (int v = 1; v <= n; v++) if (inflow[v] == 0) queue[qt++] = v; while (qh < qt) { int v = queue[qh++]; for (int e = head[v]; e != -1; e = next[e]) { int b = to[e]; ways[b] = (ways[b] + ways[v]) % MOD; if (--inflow[b] == 0) queue[qt++] = b; } } /* 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다 */ long long total = 0; for (int v = 1; v <= n; v++) if (head[v] == -1) total = (total + ways[v]) % MOD; printf("%lld\n", total); return 0;}MOD = 1000000007;첫줄 = 控制台.读数字();n = 첫줄[0];m = 첫줄[1]; // 목록은 10,000칸까지라 칸 번호에서 1을 빼 0번부터 둔다down = []; // down[a] = a에서 물이 흘러가는 칸들(물길마다 한 번씩)循环 (v = 0; v < n; v++){ down.添加([]);}inflow = 新列表(n, 0); // 아직 계산하지 않은, 들어오는 물길의 수循环 (i = 0; i < m; i++){ 물길 = 控制台.读数字(); down[물길[0] - 1].添加(물길[1] - 1); inflow[물길[1] - 1] += 1;} // 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다)ways = 新列表(n, 0); // ways[v] = 1번에서 v까지 흐르는 방법의 수(MOD로 나눈 나머지)ways[0] = 1;queue = [];循环 (v = 0; v < n; v++){ 如果 (inflow[v] == 0) { queue.添加(v); }}循环 (head = 0; head < queue.数量; head++){ v = queue[head]; 遍历 (next 在 down[v]) { ways[next] = (ways[next] + ways[v]) % MOD; // 두 수 모두 MOD보다 작아 합이 2^53보다 훨씬 작다 inflow[next] -= 1; 如果 (inflow[next] == 0) { queue.添加(next); } }}// 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다total = 0;循环 (v = 0; v < n; v++){ 如果 (down[v].数量 == 0) { total = (total + ways[v]) % MOD; }}控制台.输出(total);