Bessie đang trở về sau một chuyến đi dài ở nước ngoài tới đảo Guernsey, và Farmer John muốn treo một tấm biểu ngữ "Chào mừng về nhà" thật đẹp để đón cô. Cánh đồng của Farmer John có kích thước nguyên \(M \times N\) (\(1 \leq M, N \leq 100\,000\)), và ông đã dựng một cột tại mọi điểm có tọa độ nguyên trong cánh đồng (nếu ta gán một hệ tọa độ cho cánh đồng sao cho \((0,0)\) là góc dưới bên trái và \((M,N)\) là góc trên bên phải). Trong số \((M+1) \times (N+1)\) điểm này, Farmer John phải chọn hai điểm làm hai đầu của tấm biểu ngữ.

Vốn là người cầu toàn, Farmer John yêu cầu tấm biểu ngữ phải hoàn toàn thẳng. Điều này có nghĩa là với hai cột ông chọn, không được có bất kỳ cột nào khác nằm trên đoạn thẳng mà tấm biểu ngữ tạo thành giữa chúng. Ngoài ra, Farmer John muốn tấm biểu ngữ có độ dài ít nhất \(L\) và nhiều nhất \(H\) (\(1 \leq L \leq H \leq 150\,000\)). Farmer John cần bạn giúp tìm xem có bao nhiêu cách treo biểu ngữ. Tấm biểu ngữ có thể đảo chiều, nên việc hoán đổi hai đầu của nó vẫn được tính là cùng một cách treo. Vì con số này có thể rất lớn, Farmer John chỉ muốn biết kết quả modulo \(B\) (\(1 \leq B \leq 1\,000\,000\,000\)).

Xét ví dụ dưới đây với \(M=2\) và \(N=2\):

* * *
* * *
* * *

Farmer John muốn độ dài của tấm biểu ngữ nằm trong đoạn từ 1 đến 3, kể cả hai đầu. Mọi cách chọn cột đều thỏa mãn yêu cầu về độ dài này, nhưng lưu ý rằng không thể chọn tám cặp sau:

• \((0,0)\) và \((2,0)\): \((1,0)\) nằm trên đoạn thẳng giữa chúng.
• \((0,1)\) và \((2,1)\): \((1,1)\) nằm trên đoạn thẳng giữa chúng.
• \((0,2)\) và \((2,2)\): \((1,2)\) nằm trên đoạn thẳng giữa chúng.
• \((0,0)\) và \((2,2)\): \((1,1)\) nằm trên đoạn thẳng giữa chúng.
• \((0,0)\) và \((0,2)\): \((0,1)\) nằm trên đoạn thẳng giữa chúng.
• \((1,0)\) và \((1,2)\): \((1,1)\) nằm trên đoạn thẳng giữa chúng.
• \((2,0)\) và \((2,2)\): \((2,1)\) nằm trên đoạn thẳng giữa chúng.
• \((0,2)\) và \((2,0)\): \((1,1)\) nằm trên đoạn thẳng giữa chúng.

Do đó, tổng cộng có \(\binom{9}{2}-8=28\) cách chọn vị trí.

Dữ liệu vào

Dòng đầu tiên chứa năm số nguyên cách nhau bởi dấu cách: \(M\), \(N\), \(L\), \(H\) và \(B\).

Dữ liệu ra

In ra một số nguyên biểu thị số tấm biểu ngữ có thể treo (modulo \(B\)).

Ví dụ

2 2 1 3 100

28

Nguồn

USACO 2012 March Contest, Gold Division — Large Banner. Tác giả đề: Nathan Pinsker (2010).

https://usaco.org/index.php?page=viewproblem2&cpid=127