Especial 0-1 String
Time Limit: 1000ms
Memory Limit: 65536kb
DescriptionAssuming 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.
InputInput a number T in the first line,representing T test cases below. Then each case only contains a number L (3<=L<=1000000000).
OutputOutput the correct answer.
2 3 5
Hintwhen L=3,Legal strings are as follows: 000,001,010,011,100,110,111.