Count the number of Special Strings of a given length N | Python3 program to count the number of special strings of a given length N ; Function to return count of special strings ; Stores the answer for a particular value of n ; For n = 0 we have empty string ; For n = 1 we have 2 special strings ; Calculate count of special string of length i ; fib [ n ] stores the count of special strings of length n ; Driver code ; Initialise n
mod = 1000000007 NEW_LINE def count_special ( n ) : NEW_LINE INDENT fib = [ 0 for i in range ( n + 1 ) ] NEW_LINE fib [ 0 ] = 1 NEW_LINE fib [ 1 ] = 2 NEW_LINE for i in range ( 2 , n + 1 , 1 ) : NEW_LINE INDENT fib [ i ] = ( fib [ i - 1 ] % mod + fib [ i - 2 ] % mod ) % mod NEW_LINE DEDENT return fib [ n ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 3 NEW_LINE print ( count_special ( n ) ) NEW_LINE DEDENT