Nước X có \(N\) thành phố được đánh số từ \(1\) đến \(N\). Hệ thống giao thông có \(M\) con đường một chiều: con đường \(u \to v\) cho phép đi từ thành phố \(u\) đến thành phố \(v\). Do các con đường đều đã được quy hoạch rõ ràng từ khu vực phát triển trước sang khu vực phát triển sau, bản đồ hệ thống đảm bảo không tạo vòng khép kín.

Một công ty vận tải muốn xây dựng \(Q\) dịch vụ vận chuyển. Đối với dịch vụ thứ \(i\), họ cần biết số cách đi từ thành phố \(a_i\) đến thành phố \(b_i\) sử dụng đúng các con đường một chiều. Hỏi đáp án cho từng dịch vụ là bao nhiêu?

Vì số cách có thể rất lớn, mỗi đáp án cần in ra phần dư khi chia cho \(10^9 + 7\).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5\), \(0 \le M \le 10^5\), \(N + M \le 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả con đường một chiều từ \(u\) sang \(v\) (\(u \ne v\)).
• Dòng tiếp theo chứa số nguyên \(Q\) (\(1 \le Q \le 10^4\)).
• \(Q\) dòng cuối, mỗi dòng chứa hai số nguyên \(a_i, b_i\) mô tả một truy vấn (\(1 \le a_i, b_i \le N\)).

Định dạng đầu ra

• \(Q\) dòng, mỗi dòng là đáp số cho truy vấn tương ứng theo thứ tự vào, modulo \(10^9 + 7\).

Ví dụ

Input:

5 5
1 2
1 3
2 4
3 4
4 5
3
1 5
1 4
3 5

Output:

2
2
1

Giải thích:

• Từ \(1\) đến \(5\): hai cách đi (\(1 \to 2 \to 4 \to 5\) và \(1 \to 3 \to 4 \to 5\)).
• Từ \(1\) đến \(4\): hai cách (\(1 \to 2 \to 4\) và \(1 \to 3 \to 4\)).
• Từ \(3\) đến \(5\): một cách (\(3 \to 4 \to 5\)).

Ràng buộc

• \(1 \le N \le 10^5\)
• \(0 \le M \le 10^5\)
• \(N + M \le 10^5\)
• \(1 \le Q \le 10^4\)
• Bản đồ đảm bảo không tạo vòng khép kín.
• Mỗi đáp số in theo modulo \(10^9 + 7\).