큰 현수막

베시가 오랜 해외 여행을 마치고 돌아옵니다. 농부 존은 그녀를 맞이하려고 멋진 "환영합니다" 현수막을 걸려고 합니다. 존의 밭은 정수 크기 $M \times N$ ($1 \le M, N \le 100{,}000$)이며, 왼쪽 아래 모서리를 $(0, 0)$, 오른쪽 위 모서리를 $(M, N)$으로 하는 좌표계에서 정수 좌표를 가지는 모든 점에 기둥이 하나씩 세워져 있습니다. 이 $(M + 1) \times (N + 1)$개의 기둥 중에서 존은 현수막의 양 끝점이 될 두 기둥을 골라야 합니다.

완벽주의자인 존은 현수막이 완전히 곧게 걸리기를 원합니다. 즉, 고른 두 기둥을 잇는 선분 위에 다른 기둥이 하나라도 놓여 있으면 안 됩니다. 예를 들어 기둥 $(0, 0)$과 $(2, 0)$은 함께 고를 수 없는데, 두 점 사이에 기둥 $(1, 0)$이 놓여 있기 때문입니다.

또한 현수막의 길이는 $L$ 이상 $H$ 이하 ($1 \le L \le H \le 150{,}000$)여야 하며, 길이는 두 끝점 사이의 유클리드 거리입니다.

현수막은 뒤집을 수 있으므로 두 끝점을 서로 바꾸어도 같은 방법으로 봅니다. 존이 현수막을 걸 수 있는 서로 다른 방법의 수를 구하세요. 이 수가 매우 클 수 있으므로 $B$ ($1 \le B \le 1{,}000{,}000{,}000$)로 나눈 나머지를 출력하세요.

다섯 개의 정수 $M$, $N$, $L$, $H$, $B$가 공백으로 구분되어 한 줄에 주어집니다.

현수막을 걸 수 있는 방법의 수를 $B$로 나눈 나머지를 한 줄에 출력합니다.