split-reaction

Walter White is a great chemist.He watched Batman vs Superman and decided to study nuclear fission properties of nucleus of Kryptonite.  

He observes that when the reaction is performed at temperature T1 the number of nuclei after time t follows the pattern
f(t)=f(t-2)+t,f(0)=1,f(1)=3
and when the reaction is performed at temperature T2 the number of nuclei after time t follows the pattern
g(t)=g(t-3)+f(t),g(0)=1,g(1)=3,g(2)=7

Help Walter White in breaking the pattern so that he can earn back his position at Grey Matter Technologies.

Note:
The reaction starts at time t=0
f(t) is number of nuclei after time t when reaction is performed at T1 and
g(t) is number of nuclei after time t when reaction is performed at T2.

Input:-
First line contains a single integer T denoting number of test cases
Next T lines contains a single integer t.

Output:
Output T lines where each line contains two space seperated integers  denoting f(t)mod (10^9+7) and g(t)mod (10^9+7)

Constraints:
1 ≤ T ≤ 2500
0 ≤ t ≤ 10^{10}

Problem Setter : Teja Vojjala

SAMPLE INPUT
2
4
5

SAMPLE OUTPUT
7 10
11 18

Source: hackerearth | Difficulty: EASY


Solutions: