We can solve the above problem by recursion. The idea is place '0' or '1' as the last character and recur for the remaining length. So, we will start by placing 0 as the first character and 1 as the first character.

Result = f(0,1,n) + f(1,1,n)

The function arguments are,

f(last,index,length)

Where last is the last digit, index is the current index and length is the sequence length.

So, we have two choice initially,

1. Put 0 at the 0th index and recur for rest of the length, thus last is 0 and index is 1
2. Put 1 at the 1st index and recur for rest of the length, thus last is 1 and index is 1

Below is the details of the recursive function

int MOD=1000000007

Function f(int last ,int index,int length)
    // base case
    if(i==n)
        return 1;
    
    if(last==0 )
        then we can both use 0 and 1 as our current digit, so,
        return (f(0,index+1,n)%MOD + f(1,index+1,n)%MOD)%MOD;   
    else 
        only placing 0 is feasible since we can't allow contiguous 1
        return f(0,index+1,n)%MOD;    
End Function

Since it will generate many over lapping sub-problems, we need to use Dynamic programming to store the already computed sub problems. Below is the memorization approach.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
int dp[101][2];

long long int myrecur(int i, int last, int n)
{
    // base case
    if (i >= n)
        return 1;

    // memoization by not computing the 
    // subproblems computed already
    if (dp[i][last] != -1) 
        return dp[i][last];

    // store subproblem results
    if (last == 0) {
        dp[i][last] = (myrecur(i + 1, 0, n) % MOD + myrecur(i + 1, 1, n) % MOD) % MOD;
    }
    else {
        dp[i][last] = myrecur(i + 1, 0, n) % MOD;
    }

    return dp[i][last];
}

long long int countofSequence(int n)
{
    //initialize the dp store
    for (int i = 0; i <= n; i++) {
        dp[i][0] = -1;
        dp[i][1] = -1;
    }
    return (myrecur(1, 0, n) % MOD + myrecur(1, 1, n) % MOD) % MOD;
}

int main()
{
    int t, n, item;
    
    cout << "Enter number of testcases\n";
    cin >> t;
    
    for (int i = 0; i < t; i++) {
        cout << "Enter sequence length\n";
        cin >> n;
        cout << "Numbder of possible sequence is: " << countofSequence(n) << endl;
    }

    return 0;
}

Output:

Enter number of testcases
3
Enter sequence length
3
Numbder of possible sequence is: 5
Enter sequence length
2
Numbder of possible sequence is: 3
Enter sequence length
55
Numbder of possible sequence is: 435293607