1829: Easy Counting

Let Σ be an alphabet, a non-empty finite set. Elements of Σ are called symbols or characters. A string over Σ is any finite sequence of characters from Σ. The length of a string is the number of characters in the string (the length of the sequence) and can be any non-negative integer. The empty string is the unique string over Σ of length 0, and is denoted ε or λ. A string s is said to be a substring or factor of t if there exist (possibly empty) strings u and v such that t = usv. Now we have know that Σ = {0, 1}, and we want to know how many different string satisfy that the length of the string is n and none of substring is “110”.

The input is a sequence of datasets. A dataset is a line containing one integer n ( 1<=n<=1000000000).

The output should be composed of lines, each corresponding to an input dataset. . Since the number can be extremely big, you are only required to output the answer mod 19870907. No extra characters (e.g. extra spaces) should appear in the output.

3
4
5
6

7
12
20
33

The length of 3 is “000”, “001”, “010”, “011”, “100”, “101” and “111”.