문제
N(1≤N≤2,000)개의 줄자가 주어졌을 때, 줄자들을 몇개를 골라서 일렬로 늘어놓았을 경우에의 길이가 정수 F(1≤F≤1,000)로 나눌 수 있는 경우가 몇가지인지 알아보는 프로그램을 작성하자.
줄자의 길이는 양의 정수이며 1이상 10,000이하다.
만약 1, 2, 2, 8의 줄자가 주어졌을 때 F=5일 경우에는, 다음과 같은 경우가 가능하다. { 1, 2, 2 }, { 2, 8 }, { 2, 8 } { 2, 8 }의 경우 2의 길이의 줄자가 2개 있기 때문에 두 가지 경우가 생긴다.
입력
입력의 첫 번째 줄에는 N과 F가 입력된다.그 다음 줄부터 N개의 줄에는 줄자의 길이가 한 줄에 하나씩 입력된다.
출력
F로 나눠질 수 있는 줄자들의 길이의 합의 경우의 수를 100,000,000로 나눈 나머지를 출력한다.
예제
4 5
1
2
8
2
3
로그인해야 코드를 작성할 수 있어요.