Bedao Regular Contest 05 - CCAKE

View as PDF

Submit solution


Points: 0.70 (partial)
Time limit: 1.5s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Hôm nay là một ngày rất đặc biệt - sinh nhật của ~Copium~. Vì vậy, mẹ ~Copium~ đã quyết định tổ chức một bữa tiệc thật hoành tráng để chúc mừng sinh nhật con trai mình và mời tất cả mọi người trong làng đến tham dự.

Do quy mô bữa tiệc rất lớn nên chiếc bánh sinh nhật được mẹ ~Copium~ chuẩn bị cũng rất đặc biệt. Cụ thể, chiếc bánh là một hình chữ nhật khổng lồ có kích thước ~N \times M~. Biết tin, ~Copium~ băn khoăn không biết chia bánh như thế nào cho hợp lý. Sau ~7749~ bước suy nghĩ, ~Copium~ quyết định dùng đúng ~X~ đường cắt ngang và ~Y~ đường cắt dọc để chia chiếc bánh thành những miếng bánh nhỏ hơn. (Tất cả đường cắt đều song song với cạnh chiếc bánh.)

Để chiếc bánh trông thật ngon và chia đều được cho mọi người thì:

  • Không có ~2~ đường cắt nào trùng nhau.
  • Mọi đường cắt ngang có độ dài bằng ~M~, mọi đường cắt dọc có độ dài bằng ~N~.
  • Mỗi miếng bánh là một hình chữ nhật có độ dài ~2~ cạnh đều là số nguyên dương và diện tích ~\ge S~.

~Copium~ cảm thấy bài toàn này quá đơn giản, cậu nghĩ ra được một bài toán khó hơn đó là đếm số cách chia bánh thỏa mãn các điều kiện trên. Mặc dù thông minh thật nhưng ~Copium~ không tài nào đếm được do số cách chia quá lớn. Là một lập trình viên pro, bạn hãy lập trình giúp ~Copium~ giải bài toán này nhé.

Lưu ý:

  • Do số cách chia quá lớn nên kết quả in ra là phần dư của đáp án khi chia cho ~10^9 + 7~.
  • ~2~ cách chia được gọi là khác nếu nhau nếu có ít nhất ~1~ đường cắt dọc hoặc ~1~ đường cắt ngang ở vị trí khác nhau.

Input

  • Dòng đầu tiên chứa số nguyên ~t~ là số lượng truy vấn ~(1 \le t \le 10^4)~.
  • ~t~ dòng tiếp theo, dòng thứ ~i~ gồm ~5~ số nguyên ~N, M, X, Y, S~ là ~5~ số nguyên thể hiện truy vấn thứ ~i~ ~(1 \le N, M, X, Y, S \le 10^6)~.

Output

  • In ra ~t~ dòng, mỗi dòng một số nguyên là kết quả của truy vấn tương ứng.

Scoring

  • ~40\%~ số test có ~t \le 10~.
  • ~60\%~ số test còn lại không có điều kiện gì thêm.

Sample Input

1
3 3 2 2 1

Sample Output

1

Comments

Please read the guidelines before commenting.


There are no comments at the moment.