Sau khi đánh lừa được tên Orc Cổ Đại, cánh cổng thành nặng nề rên rỉ mở ra. Trước mắt các bạn không phải là một con đường rộng mở, mà là một hành lang dài hun hút, tối tăm và lạnh lẽo, dẫn thẳng vào trung tâm Cung Điện Hổ Phách.

Hai bên vách tường của hành lang này được khảm một dãy những hốc đèn làm bằng pha lê đen, tổng cộng có ~N~ hốc đèn được đánh số từ 1 đến ~N~.

Theo những ghi chép cổ xưa của nhà hiền triết, đây là hệ thống phòng thủ "Tiếng Thét Hư Không". Những chiếc đèn này không cháy bằng lửa, mà bằng năng lượng linh hồn. Tuy nhiên, hệ thống này có một quy tắc chết người về sự ổn định:

"Ánh sáng không được chạm vào ánh sáng. Nếu hai hốc đèn liền kề nhau cùng được thắp sáng, sự cộng hưởng năng lượng sẽ tạo ra một tiếng thét sóng âm khủng khiếp, phá nát màng nhĩ của bất kỳ ai đang đứng trong hành lang và chôn vùi họ dưới đống đổ nát."

Khi các bạn bước vào, các bạn nhận thấy tại hốc đèn thứ ~p~, ngọn lửa linh hồn đang cháy rực rỡ. Nó dường như là ngọn đèn vĩnh cửu dẫn lối, không thể bị dập tắt.

Để đi qua hành lang an toàn, các bạn cần kích hoạt hệ thống đèn để soi sáng đường đi, nhưng tuyệt đối không được kích hoạt bẫy âm thanh. Nhà hiền triết cần tính toán xem có tất cả bao nhiêu cách thiết lập trạng thái (Sáng/Tắt) cho toàn bộ ~N~ hốc đèn, biết rằng hốc đèn thứ ~p~ bắt buộc phải Sáng, và không có bất kỳ hai hốc đèn Sáng nào nằm cạnh nhau.

Hãy giúp nhà hiền triết tính toán con số này để mở khóa cơ chế an toàn của hành lang.

Input

Dòng đầu tiên chứa số nguyên ~T \left(1 \leq T \leq 2 \times 10^4 \right)~ là số test case. ~T~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên:

• ~N \left(1 \leq N \leq 45 \right)~ là số hốc đèn.
• ~p \left(1 \leq p \leq N \right)~ là vị trí đèn bắt buộc Sáng.

Đề đảm bảo tổng các N của mỗi test case sẽ ~\leq 2 \times 10^5~

Output

In ra ~T~ dòng, mỗi dòng chứa một số nguyên là kết quả của phép chia lấy dư của các cách thiết lập trạng thái với ~10^9 + 7~.

6
7 7
4 4
10 8
4 3
5 3
1 1

13
3
42
2
4
1

Note

Ví dụ với test case thứ 5, các cách thiết lập hợp lệ là:

• 00100,
• 00101,
• 10100,
• 10101.