Please code in java

Alice Likes Functions

Alice is fond of functions. Bob is jealous of her and challenges if she can solve the given function. F(N) = count of all unique possible sums made using at most two numbers from 1 to F(N-1), given F(1)=2. Alice gets confused and needs your help. Given N, you need to find out F(N) mod 1e9+7. Note: Fast IO recommended.

Input Format:

• The first line contains an integer T, denoting the number of test cases.
• Each test case consists of a single integer N in a new line.

Constraints:

1 <= T <= 1e5 1 <= N <= 1e18 

Output Format:

• Output single integer, F(N) mod 1000000007

Sample Input:

2 2 3 

Sample Output:

3 5 

Explanation: For n = 2, count of distinct sums for range {1, 2} (here F(2-1) = 2) is : 1, 2, 3(1+2). Hence, the answer is 3. For n = 3, count of distinct sums for range {1, F(2)} (here F(3-1) = 3) is : 1, 2, 3,4(1+3),5(2+3). Thus, the answer is 5.