DWITE
November 2012
Problem 3
Bitstrings

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 1's in the bitstring.
• Every run of 0's is of even length (i.e. every block of 0's has an even number of 0's in it).

1001 is an example of such a 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 being 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 being the number of different bitstrings of the corresponding length N with the described properties.

Sample Input (first 2 shown):
```
1
20
```
Sample Output (first 2 shown):
```
1
200
```