7 giờ sáng và điệp vụ Minh 12 (biệt hiệu 0069) vừa bước ra khỏi phòng ngủ của mình. Một hồi chuông réo lên từ chiếc điện thoại của anh.
"Đến nhanh lên, việc lớn rồi" - Giọng nói trong trẻo vang lên với đầy sự lo âu.
Không kịp tự pha cho mình một tách cafe hảo hạng, Minh 12 đành rảo bước ra phố, mua cho mình một cốc từ chiếc máy bán cafe tự động cũ kĩ.
Đây là một trong những phát minh của thời Liên Xô - một chiếc máy bán cafe bằng "trí tuệ". Trên máy có một chiếc màn hình, trên màn hình có một chữ cái A, đi cùng với 1 nút bấm màu đỏ và bảng số. Bấm nút, màn hình hiện chữ B. Bấm lần nữa - BA. Lần nữa, BAB. Như vậy, mỗi lần bấm phím đỏ, các chữ B đều biến thành BA, còn chữ A thì biến thành B. Bấm xong, cần phải gõ số chữ A và số chữ B để lấy cafe. Hiển nhiên càng bấm thì được càng nhiều cafe - nhưng bấm càng nhiều thì càng khó đếm - đặc biệt khi màn hình không đủ lớn để chứa tất cả kí tự.
Minh 12 muốn có một cốc cafe lớn nhất có thể - vì vậy anh muốn biết sau N lần bấm thì số kí tự A và B là bao nhiêu? Vì số có thể quá lớn nên máy chỉ yêu cầu in ra số đó mod 10^9 + 7.
Dòng đầu tiên là T, số test (T <= 10^6). T dòng tiếp theo, mỗi dòng gồm 1 số N (0 <= N <= 10^6).
Với mỗi test in trên 1 dòng 2 số là số chữ số A và số chữ số B, mod 10^9 + 7.
3
1
2
3
0 1
1 1
1 2