중복을 허용하는 집합의 개수

시간 제한2초메모리 제한128 MB

요약

1부터 T까지 값들의 개수가 주어졌을 때 크기 K(S≤K≤B)인 부분 다중집합의 개수를 1,000,000으로 나눈 나머지로 구합니다.

문제

1부터 T까지의 정수로 이루어진 수열에 총 A개의 수가 있다. 같은 값이 여러 번 나타날 수 있다.

정수 K에 대해, 주어진 A개의 수 중 정확히 K개를 골라 순서를 고려하지 않는 묶음을 만들려고 한다. 같은 값을 여러 번 고를 수는 있지만, 각 값은 입력에 등장한 횟수보다 많이 사용할 수 없다.

S ≤ K ≤ B를 만족하는 모든 K에 대해 만들 수 있는 서로 다른 묶음의 수를 모두 더하라.

이 문제에서 말하는 집합은 일반적인 수학적 집합처럼 중복을 금지하지 않는다. 중요한 것은 선택한 원소들의 순서를 바꾸어도 같은 집합으로 본다는 점이다. 두 선택은 각 값이 선택된 횟수가 모두 같을 때 같은 집합이다.

첫째 줄에 네 정수 T, A, S, B가 주어진다. 둘째 줄에는 A개의 수가 차례로 주어진다.

가능한 집합의 개수를 1,000,000으로 나눈 나머지를 출력한다.