A sparse string is a string consisting of only 0's and 1's with the constraint that it has no 2 1's consecutive.

Let A and B be two positive integers. The weight of a string is defined as A^{# 1's in the string} + B^{# 0's in the string}. Given an integer N, find the total weight of all sparse strings of length N.

Constraints : 1 ≤ A, B, N ≤ 10¹⁹.

PS: I figured out that number of sparse strings with z zeroes and o ones will be Also note that z ≥  ceil(N/2) and z ≤ N. So basically the problem reduces to finding

. I believe that the time complexity of the solution must be O(1)( a closed form solution of G_N) or O(logn)(a recurrence relation for G_N).

Can anybody provide a complete solution to the above problem?