시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 339 129 92 37.247%

문제

1부터 T(1≤T≤200)까지의 범위에 있는 수들이 총 A개 있다. 이들 중 K개를 골라서 집합을 만들 때, 가능한 집합의 개수를 세려 한다. 단, K의 범위는 1≤S≤K≤B≤A로 한다. 즉, 두 정수 S, B를 입력받아서 K=S일 경우, …, K=B일 경우의 집합의 개수를 모두 더하려고 한다.

예를 들어 T=3, 수들이 1, 1, 2, 2, 3인 경우를 생각해 보면, 각기 다음의 경우가 있다.

  • K=1 : {1}, {2}, {3}
  • K=2 : {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}
  • K=3 : {1, 1, 2} {1, 1, 3} {1, 2, 2} {1, 2, 3} {2, 2, 3}
  • K=4 : {1, 2, 2, 3} {1, 1, 2, 2} {1, 1, 2, 3}
  • K=5 : {1, 1, 2, 2, 3}

따라서 S=2, B=3일 경우의 답은 10이 된다.

우리가 일반적으로 이야기하는 집합은 같은 원소를 허용하지 않는다. 이 문제에서의 집합은 같은 원소가 없다는 사실 보다는, 집합의 각 원소들의 순서를 바꾸어도 같은 집합이라는 사실에 주목하여 풀도록 한다. 즉, {1, 1, 2}는 하나의 집합이고, {1, 2, 1}은 이와 같은 집합이다.

입력

첫째 줄에 네 정수 T, A, S, B가 주어진다. 다음 A개의 줄에는 차례로 각각의 수들이 주어진다. (A<=4000)

출력

첫째 줄에 답을 1,000,000으로 나눈 나머지를 출력한다.

예제 입력

3 5 2 3
1 2 2 1 3

예제 출력

10

힌트