레이팅 미적용베시(Bessie)가 건지 섬으로의 긴 해외여행에서 돌아오는 길이라, 농부 존(Farmer John)은 베시의 도착을 맞아 멋진 "어서 와" 현수막을 걸고 싶어 한다. 농부 존의 들판은 정수 크기 M x N (1 <= M, N <= 100,000)이며, 존은 들판에 좌표계를 부여했을 때 ((0,0)이 왼쪽 아래 꼭짓점, (M,N)이 오른쪽 위 꼭짓점) 정수 좌표를 가지는 모든 가능한 지점에 기둥을 설치해 두었다. 이 (M+1) * (N+1)개의 지점 중, 농부 존은 두 개를 현수막의 양 끝점으로 골라야 한다.
완벽주의자인 농부 존은 현수막이 완전히 팽팽하게 펴져야 한다고 고집한다. 이는 존이 고른 두 기둥 사이에 현수막이 이루는 선분 위에 다른 기둥이 있어서는 안 된다는 뜻이다. 또한 농부 존은 현수막의 길이가 L 이상 H 이하 (1 <= L <= H <= 150,000)이기를 원한다. 농부 존이 현수막을 걸 수 있는 가능한 방법의 수를 알아내는 데 당신의 도움이 필요하다. 현수막은 뒤집을 수 있으므로, 현수막의 양 끝점을 서로 바꾸는 것은 같은 방법으로 센다. 이 수는 매우 클 수 있으므로, 농부 존은 그 수를 B (1 <= B <= 1,000,000,000)로 나눈 나머지만 알고 싶어 한다.
M = 2, N = 2인 아래 예시를 생각해 보자. 기둥은 9개이다. 농부 존은 현수막의 길이가 1 이상 3 이하이기를 원한다. 어떤 기둥 쌍을 골라도 이 길이 조건은 만족하지만, 여덟 개의 쌍은 두 기둥 사이의 선분 위에 다른 기둥이 있어서 고를 수 없다. 따라서 가능한 위치는 총 (9 choose 2) - 8 = 28가지이다.
첫째 줄: 공백으로 구분된 다섯 정수 M, N, L, H, B.
가능한 현수막의 수를 B로 나눈 나머지를 나타내는 정수 하나.
banner.in · 출력을 쓸 파일 banner.out2 2 1 3 10028