I also tried to solve using DP, but managed to score 40 points only. I tried lots of optimisations but nothing helped. As you know **fibonacci mod** is a periodic sequence and for **mod = 99991**, the **period = 33330**. So if the keys in set are in range 10<sup>9</sup> we can reduce it to **key 33330** and fibonacci numbers can be computed upto 33330^{th} term easily using simple recurrence **fib[n] = fib[n - 1] + fib[n - 2]**, without matrix exponentiation because of large values of keys in the set. Then simple recurrence can give the required sum.

Consider the Fibonacci Matrix **F(n)**

\left[\begin{array}{cc}F(i - 1) & F(i) \\ F(i) & F(i + 1)\end{array}\right]

Consider the Solution Matrix **Z[n][k]**

\left[\begin{array}{cc}S(i - 1) & S(i) \\ S(i) & S(i + 1)\end{array}\right]

So, the recurrence is, **Z[k][n] = F[k] * Z[k - 1][n - 1] + Z[k][n - 1]**

Now note that we don’t need 2x2 matrix for multiplication, as **F[1][0] = F[0][1]** and **F[1][1] = F[0][0] + F[0][1]**, So lets see the multiplication **R = F x Z**

R[0][0] = F[0][0] * Z[0][0] + F[0][1] * Z[1][0]

= **F[0][0] * Z[0][0] + F[0][1] * Z[0][1]** (Because Z[1][0] = Z[1][0])

R[0][1] = F[0][0] * Z[0][1] + F[0][1] * Z[1][1]

= **F[0][0] * Z[0][1] + F[0][1] * (Z[0][0] + Z[0][1])** (Because Z[1][1] = Z[0][0] + Z[0][1])

**R[1][0] = R[0][1]**

**R[1][1] = R[0][0] + R[0][1]**

Now the next thing is that 1 <= k <= n, so basically we need **Z[10**^{5}][10^{5}] sized 2x2 Matrix. But as we can reduce matrix computation as explained above, we need **Z[10**^{5}][10^{5}][2] and this is not possible, because the array size is too large. But if we see the recurrence we just need the result of **(k - 1) cardinality subsets** for computing the result for **k cardinality subsets**, So we can just do the computation using **Z[10**^{5}][2][2] and when n is odd, then Z[][0][] gives the previous step result, and when n is even Z[][1][] gives the previous level result.

This is how I computed the values.

```
z[0][0][0] = 1;
z[0][1][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
z[j][i & 1][0] = f[i][0] * z[j - 1][(i + 1) & 1][0] + f[i][1] * z[j - 1][(i + 1) & 1][1];
z[j][i & 1][1] = f[i][0] * z[j - 1][(i + 1) & 1][1] + f[i][1] * (z[j - 1][(i + 1) & 1][0] + z[j - 1][(i + 1) & 1][1]);
z[j][i & 1][0] += z[j][(i + 1) & 1][0];
z[j][i & 1][1] += z[j][(i + 1) & 1][1];
z[j][i & 1][0] %= mod;
z[j][i & 1][1] %= mod;
}
}
```

And **Z[k][n & 1][1]** is the result.

http://www.codechef.com/viewsolution/7206298