Another Fibonacci MOREFB

All submissions for this problem are available.<h3> Read problems statements in Mandarin Chinese and Russian.</h3>

Apurva is obsessed with Fibonacci numbers. She finds Fibonacci numbers very interesting. Fibonacci numbers can be defined as given below.

Fib(1) = 1 , Fib(2) = 1.

Fib(n) = Fib(n-1) + Fib(n-2) for n > 2 .

Given a set S having N elements and an integer K, She wants to find out the value of FIBOSUM(S).

Where sum(s) represents the sum of elements in set s.

Note that values might be repeated in the set, two subsets will be called different if there is an index i such that S[i] is occurring in one of the subset and not in another.

As the value of FIBOSUM(S) can be very large, print it modulo 99991.

Input

• First line of input contains two integer N and K sepeated by a space.
• Next line contains N space separated integers denoting the set S.

Output

Print a single integer representing the answer.

Constraints

1 ≤ K ≤ N

Subtask #1: 10 points

• 1 ≤ N ≤ 20, 1 ≤ value in set ≤ 10⁹

Subtask #2: 30 points

• 1 ≤ N ≤ 2000, 1 ≤ value in set ≤ 10⁹

Subtask #3: 60 points

• 1 ≤ N ≤ 50000, 1 ≤ value in set ≤ 10⁹

Example

Input:
3 1
1 2 3

Output:
4

Explanation

FIBOSUM(S) = Fib(1) + Fib(2) + Fib(3) = 4.