Bạn được cho một dãy số A gồm vô hạn phần tử thỏa mãn điều kiện sau:

• A_i = C nếu i=1

• A_i= 3 * A_i-1 + 4 nếu i > 1

Bạn được cho 2 số nguyên N và C. Hãy tìm số hạng A_N

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương T là số lượng bộ dữ liệu

• T dòng tiếp theo, mỗi dòng gồm hai số nguyên dương N và C

Kết quả

Gồm T dòng, mỗi dòng in ra một số nguyên dương là kết quả của bài toán (Kết quả lấy phần dư cho 10⁹ + 7).

Giới hạn

• 1 ≤T≤ 10⁵

• 1 ≤ N ≤ 10¹⁸

• 1 ≤ C≤ 10⁹