Counting Valid Codewords

You are given an integer n representing the length of a binary string. Your task is to determine the number of binary strings of length n which do not contain three consecutive '1's.

A binary string is considered valid if it does not contain the substring 111. The recurrence relation for the number of valid codewords is given by:

\(dp(n)=dp(n-1)+dp(n-2)+dp(n-3)\) for \(n \ge 4\), with the base cases:

• \(dp(1)=2\)
• \(dp(2)=4\)
• \(dp(3)=7\)

Your solution should compute dp(n) based on the above recurrence and output the result.

inputFormat

The input consists of a single integer n read from standard input, which represents the length of the binary string.

outputFormat

Output a single integer to standard output which represents the number of valid codewords of length n.

1

2