How to solve this Recurrence equations using matrix exponentiation for large n (n < 109) with modulo 106 :

With base cases as 
How to solve this recurrence using matrix exponentiation
How to solve this Recurrence equations using matrix exponentiation for large n (n < 109) with modulo 106 :

With base cases as 