### PROBLEM LINK:

**Author:** Amit Pandey

**Tester:** Mahbubul Hasan and Sunny Aggarwal

**Editorialist:** Balajiganapathi Senthilnathan

**Russian Translator:** Sergey Kulik

**Mandarian Translator:** Minako Kojima

### DIFFICULTY:

Medium-Hard

### PREREQUISITES:

FFT, Divide and conquer

### PROBLEM:

Given a set S with N elements and a number K, find \sum_{s \subset S \land |s| = k} Fibo(sum(s))

### SHORT EXPLANATION

Since this is modulo a prime for which square root of 5 exists, we can calculate the n^th fibonacci number modulo P as: a(b^n - c^n) mod P for the correct values of a, b and c. Then finding the answer boils down to finding the coefficient of x^{(N - K)} in the equation (x + b^{a_1}) * (x + b^{a_2}) * .. * (x + b^{a_N}). The multiplication can be done using FFT.

### EXPLANATION:

Note that mod = 99991 is a prime number. There is a closed form for finding the n^{th} fibonacci number:

F_n = \frac{\sqrt{5}}{5}((\frac{1 + \sqrt{5}}{2})^{n} - (\frac{1 - \sqrt{5}}{2})^{n})

Now since we are taking everything modulo mod, we can calculate each of the term modulo mod.

So we will get an equation of the form:

F_n = a(b^n - c^n)

Where a, b and c are the corresponding values from the above equation modulo mod.

Now let us use this information to calculate the coefficient of b.

For example, if S = {1, 2} and K = 1, then the answer is F_1 + F_2 = a((b^1 + b^2) - (c^1 + c^2)). Let us call the part with b g(b). We will discuss how to calculate g(b), calculating for the c part is similar.

Let us see the multiplication of (x + b^1)(x + b^2). It comes out to be x^2 + (b^1 + b^2) x + b^3. Note that the coefficient of x is the answer we require. Also, if K were 2, then the answer would have been F_3 whose g(b) would be the coefficient of x^0. Seeing this pattern we can generalize the idea.

The g(b) for any K is the coefficient of x^{N - K} in the polynomial (x + b^{a_1}) * (x + b^{a_2}) * .. * (x + b^{a_N}).

So, how do we calculate this value? A naive implementation of the multiplication will TLE as it will take O(N^2). However we can use FFT (the tutorial is in Russian you may have to translate it first) or Karatsuba’s algorithm to speed up the multiplication.

### Time Complexity:

O(N logN logN)