Bạn được cho ~n~ bóng đèn, các bóng đèn được đánh số từ ~1~ tới ~n~.

Có bốn công tắc với các chức năng như sau:

• Công tắc ~1~: Đảo trạng thái (bật - tắt) tất cả các bóng đèn.
• Công tắc ~2~: Đảo trạng thái các bóng đèn được đánh số chẵn.
• Công tắc ~3~: Đảo trạng thái các bóng đèn được đánh số lẻ.
• Công tắc ~4~: Đảo trạng thái các bóng đèn được đánh số chia ~3~ dư ~1~ (ví dụ: ~1, 4, 7, 10, ...~).

Bạn cần bấm chính xác ~x~ lần, mỗi lần bạn bấm một trong ~4~ nút nói trên.

Xét tất cả ~4^x~ cách bấm, số trạng thái khác nhau của các bóng đèn mà bạn có thể tạo ra là bao nhiêu? Hai trạng thái được gọi là khác nhau, nếu có một bóng đèn mà trạng thái (bật/tắt) ở hai cách là khác nhau.

Vì kết quả có thể rất lớn, hãy in ra kết quả khi chia dư cho ~10^9 + 7~.

INPUT

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 10~) là số bộ test.

Với mỗi bộ test, dòng duy nhất chứa hai số nguyên dương ~n~ và ~x~ (~1 \le n, x \le 10^6~).

OUTPUT

Với mỗi bộ test, in ra kết quả trên một dòng, khi chia lấy dư cho ~10^9 + 7~.

SAMPLE INPUT

3
3 1
2 1
2 2

SAMPLE OUTPUT

4
3
4

Với test ~1~: các trạng thái có là: 000, 010, 101, 011, với ~0~ là tắt, ~1~ là bật.

Với test ~2~: các trạng thái có là: 11, 10, 01.

Với test ~3~: các trạng thái có là: 11, 10, 01, 00.