Tổng đường đi
View as PDF
Submit solution
Points:
100.00 (partial)
Time limit:
1.0s
Memory limit:
1G
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text
Cho đồ thị có hướng không chu trình và 2 đỉnh ~s,t~. Cho biết có bao nhiêu đường đi từ ~s~ đến ~t~ (hai đường đi khác nhau nếu như thứ tự các đỉnh trên chúng khác nhau)
Dữ liệu vào
- Dòng đầu tiên gồm 4 số nguyên dương ~n, m, s, t~ ~(n, m \leq 10^5, s, t \leq n)~ lần lượt là số đỉnh, số cạnh và 2 đỉnh ~s, t~ như miêu tả của đề bài
- ~m~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ~u, v~ thể hiện một cạnh đi từ ~u~ tới ~v~
Dữ liệu ra
- Một số nguyên duy nhất là số đường đi từ ~s~ tới ~t~, vì kết quả có thể rất lớn nên hãy in kết quả chia lấy dư cho ~10^9 + 7~
Ví dụ:
Input
10 14 5 7
3 2
9 7
5 4
4 10
1 5
1 2
7 6
10 6
8 3
5 8
5 10
5 3
5 9
5 2
Output
1
Comments
đáp án được mod 1e9+7 nhé và limit n,m <=1e5 nhé
cảm ơn Lộc
cho minh xin limit n,m với được hem (^-^)
dễ thương quá
'.'