소 프리스비 팀

농부 돈이 프리스비를 시작하는 모습을 본 농부 존(FJ)도 함께 즐기고 싶어졌습니다. 존은 $1$번부터 $N$번까지 번호가 매겨진 자신의 소 $N$마리 ($1 \le N \le 2000$) 중에서 프리스비 팀을 만들려고 합니다. 각 소 $i$에게는 프리스비 실력을 나타내는 능력치 $R_i$ ($1 \le R_i \le 100000$) 가 있습니다. FJ는 소 한 마리 이상을 골라 팀을 구성할 수 있습니다.

그런데 FJ는 팀을 매우 까다롭게 고르기 때문에 조건을 하나 더 두었습니다. 그가 가장 좋아하는 숫자가 $F$ ($1 \le F \le 1000$) 이므로, 팀에 속한 소들의 능력치 합이 $F$로 정확히 나누어떨어질 때만 그 팀을 받아들입니다.

존이 만들 수 있는 서로 다른 팀의 개수를 구하세요. 서로 다른 두 소가 같은 능력치를 가지더라도, 구성이 다르면 다른 팀으로 셉니다. 이 값이 매우 커질 수 있으므로, 답을 $100000000$으로 나눈 나머지를 출력하세요.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $F$
• 둘째 줄부터 $N+1$번째 줄까지: $i+1$번째 줄에는 정수 $R_i$가 하나 주어집니다

• 첫째 줄: 존이 고를 수 있는 팀의 개수를 $100000000$으로 나눈 나머지를 나타내는 정수 하나

위 예시에서 존은 $8$과 두 개의 $2$ 중 하나를 묶거나 ($8 + 2 = 10$), 두 개의 $2$와 $1$을 함께 묶을 수 있습니다 ($2 + 2 + 1 = 5$). $2$가 두 마리이므로 $8 + 2$ 조합은 서로 다른 두 팀으로 셉니다.