부분집합 합의 피보나치 수

피보나치 수는 다음과 같이 정의한다.

• $F[1] = 1$
• $F[2] = 1$
• $F[N] = F[N-1] + F[N-2]$ ($N \ge 3$)

원소가 $N$개인 집합 $S$와 정수 $K$가 주어진다. 크기가 $K$인 $S$의 부분집합 $s$마다 원소의 합 $\mathrm{sum}(s)$를 구한 다음, $F[\mathrm{sum}(s)]$를 모두 더한 값을 구하는 프로그램을 작성하시오.

예를 들어 $S = \{1, 2, 3, 4, 5\}$이고 $K = 2$이면 크기가 2인 부분집합은 $\{1, 2\}$, $\{1, 3\}$, $\{1, 4\}$, $\{1, 5\}$, $\{2, 3\}$, $\{2, 4\}$, $\{2, 5\}$, $\{3, 4\}$, $\{3, 5\}$, $\{4, 5\}$이다. 각 부분집합의 합은 차례대로 3, 4, 5, 6, 5, 6, 7, 7, 8, 9이므로 답은 $F[3] + F[4] + F[5] + F[6] + F[5] + F[6] + F[7] + F[7] + F[8] + F[9] = 112$이다.

첫째 줄에 $N$과 $K$가 주어진다. ($1 \le N \le 50\,000$, $1 \le K \le N$)

둘째 줄에 집합 $S$의 원소 $N$개가 공백으로 구분되어 주어진다. 각 원소는 $10^9$ 이하의 자연수이고, 서로 다르다.

크기가 $K$인 부분집합 $s$마다 구한 $F[\mathrm{sum}(s)]$의 합을 99991로 나눈 나머지를 첫째 줄에 출력한다.