时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Fibonacci Sequence:
In particular:
and 
are two different Fibonacci numbers.
For example:
indicates that 
corresponds to at least two Fibonacci representations.
The value of the Fibonacci representation)_%7B%7D)
: defined as the product of the Fibonacci numbers in the representation .
For example:
. In this representation, the value is: 
.
With the above definitions, now, find the sum of all Fibonacci representations’ value of a given number
.
To simplify the question, please output the answer modulo lovely
.
Fibonacci representation _%7B%7D)
: Any natural number can be expressed as the sum of a set of different Fibonacci numbers.
In particular:
For example:
The value of the Fibonacci representation
For example:
With the above definitions, now, find the sum of all Fibonacci representations’ value of a given number
To simplify the question, please output the answer modulo lovely
输入描述:
The first line contains a positive integer.
The next T line, each line has a natural number.
输出描述:
The output should containlines, each line with an integer, which represents the value of the answer modulo lovely