Fibonacci Numbers of Subset Sums

The Fibonacci numbers are defined as follows.

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

You are given a set $S$ of $N$ numbers and an integer $K$. For every subset $s$ of $S$ whose size is $K$, take the sum of its elements $\mathrm{sum}(s)$, and add up $F[\mathrm{sum}(s)]$ over all such subsets. Write a program that computes that total.

For example, take $S = \{1, 2, 3, 4, 5\}$ and $K = 2$. The subsets of size 2 are $\{1, 2\}$, $\{1, 3\}$, $\{1, 4\}$, $\{1, 5\}$, $\{2, 3\}$, $\{2, 4\}$, $\{2, 5\}$, $\{3, 4\}$, $\{3, 5\}$, $\{4, 5\}$. Their sums are 3, 4, 5, 6, 5, 6, 7, 7, 8, 9 in that order, so the total is $F[3] + F[4] + F[5] + F[6] + F[5] + F[6] + F[7] + F[7] + F[8] + F[9] = 112$.

The first line contains $N$ and $K$. ($1 \le N \le 50\,000$, $1 \le K \le N$)

The second line contains the $N$ elements of $S$, separated by spaces. Each element is a natural number at most $10^9$, and the elements are distinct.

Print on the first line the sum of $F[\mathrm{sum}(s)]$ over every subset $s$ of size $K$, modulo 99991.