Count non | C ++ implementation of the approach ; Function to pre - compute the sequence ; For N = 1 the answer will be 2 ; Starting two terms of the sequence ; Compute the rest of the sequence with the relation F [ i ] = F [ i - 1 ] + F [ i - 2 ] ; Driver code ; Pre - compute the sequence
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long NEW_LINE const ll N = 10000 ; const ll MOD = 1000000007 ; ll F [ N ] ; void precompute ( ) { F [ 1 ] = 2 ; F [ 2 ] = 3 ; F [ 3 ] = 4 ; for ( int i = 4 ; i < N ; i ++ ) F [ i ] = ( F [ i - 1 ] + F [ i - 2 ] ) % MOD ; } int main ( ) { int n = 8 ; precompute ( ) ; cout << F [ n ] ; return 0 ; }