A 'bitstring' is a string consisting of 0s and 1s. However, you're only looking for bitstrings with the following properties:

• There are no two consecutive 1s in the bitstring
• Every run of 0s is of even length (i.e. every block of 0s has an even number of 0s in it).

1001 is an example of such bitstring, but 10001 is not. Luckily, your Computer Science (or Combinatorics) teacher shares a formula for figuring out how many such bitstrings exist for any given length N:

• s(0) = 1, s(1) = 1, s(2) = 1
• s(n) = s(n-2) + s(n-3) for all n > 2

That is, there is only 1 string of size 0 (empty string matches both rules). Only 1 string of size 1 ("1"), and only 1 string of size 2 ("00"). For size 3, you'd need to calculate the sum of s(3-2) and s(3-3), which are known from the results above.

The input file DATA3.txt will contain 5 test cases, each a line with a single integer 1 <= N <= 75, the length of the bitstring.

The output file OUT3.txt will contain 5 lines of output, each the number of different bitstrings of the corresponding length N, with the described properties.

 
1
20
		        

 
1
200