| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1231
Especial 0-1 String
Time Limit: 1000ms
Memory Limit: 65536kb Description
Assuming there is a 0-1 string with its length L,what’s more,a legal 0-1 string can’t contain any sub-string as follows: '101', '10011'.For example, '10001' is a legal string,because it doesn’t contain any sub-string '101' or '10011'。But '100000101' is an illegal string,because it contains sub-string '101' Can you compute the numbers of such legal string with its length L? Maybe the result will be very huge,so divide by 20110514,then output the remaider. Input
Input a number T in the first line,representing T test cases below. Then each case only contains a number L (3<=L<=1000000000).
Output
Output the correct answer.
Sample Input
2 3 5 Sample Output
7 20 Hint
when L=3,Legal strings are as follows: 000,001,010,011,100,110,111.
|