Bạn được cho 2 mảng A và B, độ dài của 2 mảng đều là N. Mỗi mảng gồm các phần tử hoặc là số nguyên dương, hoặc là -1.
Nhiệm vụ của bạn là, tìm số cách thay mỗi số -1 bởi 1 số nguyên không âm để 2 mảng có tổng bằng nhau.
Input:
- Dòng đầu tiên là N - số phần tử của mảng.
- Dòng tiếp theo là N phần tử của mảng A.
- Dòng cuối là N phần tử của mảng B.
Output:
- Dòng duy nhất là số hữu hạn X - số cách thay (sau khi đã chia lấy dư cho 10^9+7) nếu tìm được. Nếu không tìm được X, in ra 'Infinite'.
| input | output |
4 1 2 -1 4 3 3 -1 1 |
Infinite |
4 1 2 -1 4 3 3 3 1 |
1 |
Giải thích ví dụ:
Ở test ví dụ 1, có vô số cách thay để tổng 2 mảng bằng nhau nên in ra "Infinite" (thay "-1" trong mỗi mảng thành những giá trị giống nhau)
Ở test ví dụ 2, thay -1 ở mảng A bởi số 3, ta được tổng mảng A là 10, bằng với tổng mảng B.
Giới hạn:
Trong tất cả các test: N = 105
Subtask1 (25% số điểm): Số lượng số -1 trong cả mỗi mảng bé hơn 1 và 1 <= A[i], B[i] <= 109
Subtask2 (75% số điểm): Tổng của tất cả các số trong mỗi mảng bé hơn 106