시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB88537426342.557%

문제

1부터 T까지의 범위에 있는 수들이 총 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개의 수가 차례로 주어진다.

출력

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

제한

  • 1 ≤ T ≤ 200
  • 1 ≤ A ≤ 4000
  • 1 ≤ S ≤ B ≤ A

예제 입력 1

3 5 2 3
1 2 2 1 3

예제 출력 1

10
W3sicHJvYmxlbV9pZCI6IjIwOTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5ZDFcdWQ1NjlcdWM3NTggXHVhYzFjXHVjMjE4IiwiZGVzY3JpcHRpb24iOiI8cD4xXHViZDgwXHVkMTMwIFRcdWFlNGNcdWM5YzBcdWM3NTggXHViYzk0XHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMThcdWI0ZTRcdWM3NzQgXHVjZDFkIEFcdWFjMWMgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI0ZTQgXHVjOTExIEtcdWFjMWNcdWI5N2MgXHVhY2U4XHViNzdjXHVjMTFjIFx1YzlkMVx1ZDU2OVx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHViNTRjLCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjOWQxXHVkNTY5XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWMxMzhcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWIyZTgsIEtcdWM3NTggXHViYzk0XHVjNzA0XHViMjk0IDEgJmxlOyBTICZsZTsgSyAmbGU7IEIgJmxlOyBBXHViODVjIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWI0NTAgXHVjODE1XHVjMjE4IFMsIEJcdWI5N2MgXHVjNzg1XHViODI1XHViYzFiXHVjNTQ0XHVjMTFjIEsgPSBTXHVjNzdjIFx1YWNiZFx1YzZiMCwgJmhlbGxpcDssIEsgPSBCXHVjNzdjIFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWM5ZDFcdWQ1NjlcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWIzNTRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFQ9MywgXHVjMjE4XHViNGU0XHVjNzc0IDEsIDEsIDIsIDIsIDNcdWM3NzggXHVhY2JkXHVjNmIwXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NCBcdWJjZjRcdWJhNzQsIFx1YWMwMVx1YWUzMCBcdWIyZTRcdWM3NGNcdWM3NTggXHVhY2JkXHVjNmIwXHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5LID0gMTogezF9LCB7Mn0sIHszfTxcL2xpPlxyXG5cdDxsaT5LID0gMjogezEsIDF9LCB7MSwgMn0sIHsxLCAzfSwgezIsIDJ9LCB7MiwgM308XC9saT5cclxuXHQ8bGk+SyA9IDM6IHsxLCAxLCAyfSB7MSwgMSwgM30gezEsIDIsIDJ9IHsxLCAyLCAzfSB7MiwgMiwgM308XC9saT5cclxuXHQ8bGk+SyA9IDQ6IHsxLCAyLCAyLCAzfSB7MSwgMSwgMiwgMn0gezEsIDEsIDIsIDN9PFwvbGk+XHJcblx0PGxpPksgPSA1OiB7MSwgMSwgMiwgMiwgM308XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWI1MzBcdWI3N2NcdWMxMWMgUyA9IDIsIEIgPSAzXHVjNzdjIFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWIyZjVcdWM3NDAgMTBcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2YjBcdWI5YWNcdWFjMDAgXHVjNzdjXHViYzE4XHVjODAxXHVjNzNjXHViODVjIFx1Yzc3NFx1YzU3Y1x1YWUzMFx1ZDU1OFx1YjI5NCBcdWM5ZDFcdWQ1NjlcdWM3NDAgXHVhYzE5XHVjNzQwIFx1YzZkMFx1YzE4Y1x1Yjk3YyBcdWQ1YzhcdWM2YTlcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWM3NzQgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjXHVjNzU4IFx1YzlkMVx1ZDU2OVx1Yzc0MCBcdWFjMTlcdWM3NDAgXHVjNmQwXHVjMThjXHVhYzAwIFx1YzVjNlx1YjJlNFx1YjI5NCBcdWMwYWNcdWMyZTQgXHViY2Y0XHViMmU0XHViMjk0LCBcdWM5ZDFcdWQ1NjlcdWM3NTggXHVhYzAxIFx1YzZkMFx1YzE4Y1x1YjRlNFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWI5N2MgXHViYzE0XHVhZmI4XHVjNWI0XHViM2M0IFx1YWMxOVx1Yzc0MCBcdWM5ZDFcdWQ1NjlcdWM3NzRcdWI3N2NcdWIyOTQgXHVjMGFjXHVjMmU0XHVjNWQwIFx1YzhmY1x1YmFhOVx1ZDU1OFx1YzVlYyBcdWQ0ODBcdWIzYzRcdWI4NWQgXHVkNTVjXHViMmU0LiBcdWM5ODksIHsxLCAxLCAyfVx1YjI5NCBcdWQ1NThcdWIwOThcdWM3NTggXHVjOWQxXHVkNTY5XHVjNzc0XHVhY2UwLCB7MSwgMiwgMX1cdWM3NDAgXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWM5ZDFcdWQ1NjlcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjEyNCBcdWM4MTVcdWMyMTggVCwgQSwgUywgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgQVx1YWMxY1x1Yzc1OCBcdWMyMThcdWFjMDAgXHVjYzI4XHViODQwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjJmNVx1Yzc0NCAxLDAwMCwwMDBcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBUICZsZTsgMjAwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBBICZsZTsgNDAwMDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgUyAmbGU7IEIgJmxlOyBBPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIyMDkyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQW50IENvdW50aW5nIiwiZGVzY3JpcHRpb24iOiI8cD5CZXNzaWUgd2FzIHBva2luZyBhcm91bmQgdGhlIGFudCBoaWxsIG9uZSBkYXkgd2F0Y2hpbmcgdGhlIGFudHMgbWFyY2ggdG8gYW5kIGZybyB3aGlsZSBnYXRoZXJpbmcgZm9vZC4gU2hlIHJlYWxpemVkIHRoYXQgbWFueSBvZiB0aGUgYW50cyB3ZXJlIHNpYmxpbmdzLCBpbmRpc3Rpbmd1aXNoYWJsZSBmcm9tIG9uZSBhbm90aGVyLiBTaGUgYWxzbyByZWFsaXplZCB0aGUgc29tZXRpbWVzIG9ubHkgb25lIGFudCB3b3VsZCBnbyBmb3IgZm9vZCwgc29tZXRpbWVzIGEgZmV3LCBhbmQgc29tZXRpbWVzIGFsbCBvZiB0aGVtLiBUaGlzIG1hZGUgZm9yIGEgbGFyZ2UgbnVtYmVyIG9mIGRpZmZlcmVudCBzZXRzIG9mIGFudHMhPFwvcD5cclxuXHJcbjxwPkJlaW5nIGEgYml0IG1hdGhlbWF0aWNhbCwgQmVzc2llIHN0YXJ0ZWQgd29uZGVyaW5nLiBCZXNzaWUgbm90ZWQgdGhhdCB0aGUgaGl2ZSBoYXMgVCAoMSAmbHQ7PSBUICZsdDs9IDEsMDAwKSBmYW1pbGllcyBvZiBhbnRzIHdoaWNoIHNoZSBsYWJlbGVkIDEuLlQgKEEgYW50cyBhbHRvZ2V0aGVyKS4gRWFjaCBmYW1pbHkgaGFkIHNvbWUgbnVtYmVyIE5pICgxICZsdDs9IE5pICZsdDs9IDEwMCkgb2YgYW50cy48XC9wPlxyXG5cclxuPHA+SG93IG1hbnkgZ3JvdXBzIG9mIHNpemVzIFMsIFMrMSwgLi4uLCBCICgxICZsdDs9IFMgJmx0Oz0gQiAmbHQ7PSBBKSBjYW4gYmUgZm9ybWVkPzxcL3A+XHJcblxyXG48cD5XaGlsZSBvYnNlcnZpbmcgb25lIGdyb3VwLCB0aGUgc2V0IG9mIHRocmVlIGFudCBmYW1pbGllcyB3YXMgc2VlbiBhcyB7MSwgMSwgMiwgMiwgM30sIHRob3VnaCByYXJlbHkgaW4gdGhhdCBvcmRlci4gVGhlIHBvc3NpYmxlIHNldHMgb2YgbWFyY2hpbmcgYW50cyB3ZXJlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjMgc2V0cyB3aXRoIDEgYW50OiB7MX0gezJ9IHszfTxcL2xpPlxyXG5cdDxsaT41IHNldHMgd2l0aCAyIGFudHM6IHsxLDF9IHsxLDJ9IHsxLDN9IHsyLDJ9IHsyLDN9PFwvbGk+XHJcblx0PGxpPjUgc2V0cyB3aXRoIDMgYW50czogezEsMSwyfSB7MSwxLDN9IHsxLDIsMn0gezEsMiwzfSB7MiwyLDN9PFwvbGk+XHJcblx0PGxpPjMgc2V0cyB3aXRoIDQgYW50czogezEsMiwyLDN9IHsxLDEsMiwyfSB7MSwxLDIsM308XC9saT5cclxuXHQ8bGk+MSBzZXQgd2l0aCA1IGFudHM6IHsxLDEsMiwyLDN9PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+WW91ciBqb2IgaXMgdG8gY291bnQgdGhlIG51bWJlciBvZiBwb3NzaWJsZSBzZXRzIG9mIGFudHMgZ2l2ZW4gdGhlIGRhdGEgYWJvdmUuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogNCBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IFQsIEEsIFMsIGFuZCBCPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLkErMTogRWFjaCBsaW5lIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgdGhhdCBpcyBhbiBhbnQgdHlwZSBwcmVzZW50IGluIHRoZSBoaXZlPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVGhlIG51bWJlciBvZiBzZXRzIG9mIHNpemUgUy4uQiAoaW5jbHVzaXZlKSB0aGF0IGNhbiBiZSBjcmVhdGVkLiBBIHNldCBsaWtlIHsxLDJ9IGlzIHRoZSBzYW1lIGFzIHRoZSBzZXQgezIsMX0gYW5kIHNob3VsZCBub3QgYmUgZG91YmxlLWNvdW50ZWQuIFByaW50IG9ubHkgdGhlIExBU1QgU0lYIERJR0lUUyBvZiB0aGlzIG51bWJlciwgd2l0aCBubyBsZWFkaW5nIHplcm9lcyBvciBzcGFjZXMuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2005-2006 Season > USACO November 2005 Contest > Silver ?번

  • 잘못된 조건을 찾은 사람: doju
  • 잘못된 데이터를 찾은 사람: sait2000