문제
N개의 사탕 주머니가 있고 각 사탕 주머니에는 A[i]개의 사탕이 있다. 모든 사탕은 서로 다르다.
유섭이는 사탕 주머니에서 사탕을 꺼내 먹으려고 한다. 유섭이는 하나 이상 K개 이하의 사탕을 먹을 것이며, 하나의 주머니에서는 사탕을 최대 하나만 먹을 수 있다.
유섭이가 사탕을 먹는 방법의 수를 구하는 프로그램을 작성하여라. 먹은 사탕의 집합이 다르면 다른 경우이며 사탕을 먹는 순서는 고려하지 않는다.
입력
첫 번째 줄에 N, K가 주어진다. (1 ≤ K ≤ N ≤ 3,000)
두 번째 줄에는 A[i]가 주어진다. (1 ≤ A[i] ≤ 1,000)
출력
첫 번째 줄에 유섭이가 사탕을 먹는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.
예제
4 2
1 2 3 4
45
로그인해야 코드를 작성할 수 있어요.