현수막

대학원생 석홍우는 대전에서 긴 학위과정을 마치고 돌아오고 있고, 그의 가족은 그를 맞이하기 위해 '금의환향' 현수막을 마당에 설치하고 싶어합니다. 마당의 면적은 $M \times N (1 \lt= M, N \lt= 100,000)$ 이며, 마당에 좌표를 할당하여 (0,0)이 왼쪽 아래 구석에, (M,N)이 오른쪽 위 구석에 있도록 마당의 모든 점에 막대를 설치했습니다. 이 $(M+1) * (N+1)$ 점 중에서 현수막의 두 끝점을 선택해야 합니다.

현수막은 완전히 직선이어야 합니다. 즉, 현수막 사이에 다른 막대가 있으면 안됩니다. 또한, 현수막의 길이가 최소 $L$, 최대 $H (1 \lt= L \lt= H \lt= 150,000)$가 되어야 합니다. 그들은 현수막을 걸 수 있는 가능한 방법이 몇 가지인지 알아내는 데 도움이 필요합니다. 현수막은 뒤집을 수 있으므로, 현수막의 두 끝점을 바꾸는 것이 현수막을 걸 같은 방법으로 간주됩니다. 이 수는 매우 크기 때문에 그들은 그것이 모듈로 $B (1 \lt= B \lt= 1,000,000,000)$인가를 알고 싶어합니다.

M = 2, N = 2의 경우를 예로 들어봅시다:

* * *
* * *
* * *

석홍우의 가족은 현수막의 길이가 1과 3 사이이기를 원합니다. 선택한 막대눈 길이 요구 사항을 모두 충족시킵니다. 그러나 8 쌍의 선택은 제외되어야 합니다:

• (0, 0)과 (2, 0) 사이: (1, 0)은 그 사이의 선분 위에 있습니다.
• (0, 1)과 (2, 1) 사이: (1, 1)은 그 사이의 선분 위에 있습니다.
• (0, 2)과 (2, 2) 사이: (1, 2)는 그 사이의 선분 위에 있습니다.
• (0, 0)과 (2, 2) 사이: (1, 1)은 그 사이의 선분 위에 있습니다.
• (0, 0)과 (0, 2) 사이: (0, 1)은 그 사이의 선분 위에 있습니다.
• (1, 0)과 (1, 2) 사이: (1, 1)은 그 사이의 선분 위에 있습니다.
• (2, 0)과 (2, 2) 사이: (2, 1)은 그 사이의 선분 위에 있습니다.
• (0, 2)과 (2, 0) 사이: (1, 1)은 그 사이의 선분 위에 있습니다.

따라서, 총 (9 choose 2) - 8 = 28 가능한 위치가 있습니다.

• 줄 1: 다섯 개의 공백으로 구분된 정수: M, N, L, H, B.

• 줄 1: 가능한 현수막의 수를 나타내는 하나의 정수 (B로 모듈로 연산).