Fibonacci Numbers of Subset Sums

Time limit5sMemory limit512 MB

Summary

Sum F[sum(s)] over all K-element subsets s of a set of N distinct numbers, modulo 99991.

Level: Hard8 of 10
Topics: Combinatorics, Dynamic programming, Math, Number theory
Solved: No attempts yet

Problem

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$ .

Input

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.

Output

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

Examples3

Example 1
Input
```
3 1
1 2 3
```
Expected output
```
4
```
Example 2
Input
```
5 2
1 2 3 4 5
```
Expected output
```
112
```
Example 3
Input
```
6 3
3 5 7 10 20 30
```
Expected output
```
57796
```