**Problem**: Find the coefficient of xk in (1−x−x2)-6 modulo m.

**Constraints**:  

 k≤264   

m≤105, m can be a composite number.   

I have 10^5 such queries to process in 2 sec, so O(log k) for each query solution will work.  

kth Fibonacci and [Lucas numbers](https://www.wikipedia.org/wiki/Lucas_number) can be calculated in O(log k). 

**My Approach**: I thought that closed form expression may not be possible(I have not figured out any idea till now also), but some recursive formula or algorithm may be possible.

**What I have found:**
On OEIS , I came to know that this reciprocal polynomial is generating function of convolved Fibonacci number of order 6 .   

Then I have found this paper <https://cs.uwaterloo.ca/journals/JIS/VOL7/Moree/moree12.pdf>
in which required answer is represented as sum of Fibonacci and Lucas numbers divided by powers of 5.

This is problematic since m can be a composite number(multiple of 5). I am stuck here because multiplicative inverse of powers of 5 will not exist in that case.

Please suggest me any solution for this or any other way to calculate the answer.

Thanks in advance.