# Question

consecutive 1s.

As the number can be large, return the answer modulo 10^9+7.

### Example 1:

#### Input:

N = 3#### Output:

5### Explanation:

All the binary strings of length 3 havingno consecutive 1s are "000", "001", "101",

"100" and "010".

#### Example 2:

N = 2

Output:

3

### Explanation:

All the binary strings of length 2 having noconsecutive 1s are "10", "00" and "01".

Your Task:

You don’t need to read input or print anything. Complete the function countStrings() which takes the

integer N as the input parameter, and returns the number of binary strings of length N with no

consecutive 1s.

Expected Time Complexity:

**O(log(N))**

Expected Auxiliary Space: O(Height of the recursive call stack)

Constraints:

1 ≤ N ≤ 10^18

### Approach

To solve this problem efficiently, we can use matrix exponentiation. Let's go step by step through the code to understand the solution.efficient matrix exponentiation technique used.

## Code

#include <bits/stdc++.h>

using namespace std;

class Solution {

public:

int mod = 1e9 + 7;

int fib(long long int n) {

vector<vector<long long int>> F = {{1, 1}, {1, 0}};

if (n == 0)

return 0;

power(F, n - 1);

return F[0][0];

}

void power(vector<vector<long long int>>& F, long long int n) {

if (n == 0 || n == 1)

return;

vector<vector<long long int>> M = {{1, 1}, {1, 0}};

vector<vector<long long int>> ans = {{1, 0}, {0, 1}};

while (n > 0) {

if (n % 2 == 0) {

F = multiply(F, F);

n /= 2;

} else {

ans = multiply(ans, F);

n = n - 1;

}

}

F = ans;

}

vector<vector<long long int>> multiply(vector<vector<long long int>> F, vector<vector<long long

int>> M) {

long long int x = (F[0][0] * M[0][0] + F[0][1] * M[1][0]) % mod;

long long int y = (F[0][0] * M[0][1] + F[0][1] * M[1][1]) % mod;

long long int z = (F[1][0] * M[0][0] + F[1][1] * M[1][0]) % mod;

long long int w = (F[1][0] * M[0][1] + F[1][1] * M[1][1]) % mod;

F[0][0] = x;

F[0][1] = y;

F[1][0] = z;

F[1][1] = w;

return F;

}

int countStrings(long long int N) {

return fib(N + 2);

}

};

int main() {

int t;

cin >> t;

while (t--) {

long long int N;

cin >> N;

Solution obj;

cout << obj.countStrings(N) << endl;

}

return 0;

}