[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.
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.1ms with 1 query(s).