Muallif: __thecrash__

G. Ko'chirmaslik uchun

Vaqt limiti: 1000 ms Xotira limiti: 256 mb

Imtihon kuni o'qituvchi o'quvchilarni bir-biridan ko'chirmasliklari uchun maxsus tartibda o'tqazmoqchi: hech qaysi ikki o'quvchi yonma-yon stullarda o'tirmasligi kerak.

Imtihon ikki xil xonada o'tkaziladi. Birinchi turdagi xonada \(n\) ta stul bir qatorga terilgan va chapdan o'ngga \(1\) dan \(n\) gacha raqamlangan. Bunda \(i\)-stul faqat \((i-1)\)- va \((i+1)\)-stullar bilan yonma-yon. Ikkinchi turdagi xonada \(n\) ta stul dumaloq stol atrofida joylashgan. Bu holda ham \(i\)-stul \((i-1)\)- va \((i+1)\)-stullar bilan yonma-yon, lekin qo'shimcha ravishda \(1\)- va \(n\)-stullar ham yonma-yon bo'ladi.

O'qituvchi \(k\) ta o'quvchini o'tqazishi kerak. Faqat qaysi stullar band bo'lishi muhim, ya'ni o'quvchilarning o'zaro o'rni almashsa, bu yangi usul hisoblanmaydi. O'tqazish usullari sonini toping. Javob juda katta bo'lishi mumkin, shuning uchun uni \(10^9 + 7\) ga bo'lgandagi qoldig'ini chiqaring.

O'qituvchiga \(q\) ta savol bo'yicha yordam bering.

Kiruvchi ma'lumotlar

Birinchi qatorda bitta butun son \(q\) (\(1 \le q \le 10^5\)) — savollar soni.

Keyingi \(q\) ta qatorning har birida uchta butun son \(t\), \(n\) va \(k\) berilgan (\(t \in \{1, 2\}\), \(3 \le n \le 10^6\), \(0 \le k \le n\)). Bunda \(t = 1\) stullar qatorga terilganini, \(t = 2\) esa dumaloq stol atrofida joylashganini bildiradi.

Chiquvchi ma'lumotlar

Har bir savol uchun alohida qatorda bitta son chiqaring: o'tqazish usullari sonining \(10^9 + 7\) ga bo'lgandagi qoldig'i.

Misollar

1

5
1 5 2
2 5 2
1 4 3
2 6 3
1 10 0

6
5
0
2
1

2

8
1 3 0
1 3 1
1 3 2
1 3 3
2 3 0
2 3 1
2 3 2
2 3 3

1
3
1
0
1
3
0
0