Là người bất chấp mọi quy tắc, thách thức mọi cuộc chơi, bạn Hiếu giấu giải quốc gia rất thích xáo trộn mọi thứ (không loại trừ lịch trình của chính mình) nhằm tăng độ khó cho game. Thú vị hơn, Hiếu còn có sở thích thích thay đổi vị trí của các tập hữu hạn số tự nhiên phân biệt, sau đó tìm lại một số hoán vị "đẹp" (theo một tiêu chí nào đó).

Gọi \(p = (p_1, p_2, \ldots, p_{2 \cdot n})\) là một hoán vị của \(2 \cdot n\) số tự nhiên \(1, 2, 3, \ldots, 2 \cdot n\). Là người có khả năng tìm ra trật tự trong hỗn loạn, Hiếu định nghĩa một hoán vị \(p\) là "hoán vị đẹp" khi và chỉ khi nó thỏa mãn các tính chất sau:

1. \(p_1 > p_2 > p_3 > \ldots > p_n\)
2. \(p_{2 \cdot n} < p_{2 \cdot n - 1} < \ldots < p_{n + 1}\)
3. \(p_{i} < p_{i + n}\) với mọi \(1 \le i \le n\)

Với mỗi giá trị \(n\) cho trước, số "hoán vị đẹp" là rất nhiều. Cho hai số nguyên \(n\) và \(k\), hãy tìm "hoán vị đẹp" thứ \(k\) nếu sắp xếp mọi hoán vị đẹp theo thứ tự từ điển tăng dần.

Nhắc lại: Với hai dãy \(\alpha\) và \(\beta\) cùng có độ dài \(\eta\), \(\alpha\) xếp trước \(\beta\) theo thứ tự từ điển khi và chỉ khi tồn tại một vị trí \(\iota\) \((1 \le \iota \le \eta)\) sao cho:

• \(\alpha_{\kappa} = \beta_{\kappa}\) với mọi \(1 \le \kappa \le \iota - 1\)
• \(\alpha_{\iota} < \beta_{\iota}\)

Dữ liệu

Vào từ file văn bản permutations.inp:

Dòng đầu tiên chứa một số nguyên \(\tau\) \((1\le \tau \le 987)\) là số bộ dữ liệu. Mỗi dòng tiếp theo chứa hai số nguyên \(n\) \((1\le n \le 121393)\) và \(k\) \((1 \le k \le 679891637638612258)\) mô tả một bộ dữ liệu.

Kết quả

Ghi ra file văn bản permutations.out:

Với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên theo quy tắc sau:

• Nếu không tồn tại hoán vị thứ \(k\) thỏa mãn, in ra \(-1\).
• Ngược lại, gọi hoán vị cần tìm là \(a_1, a_2, \ldots, a_{2 \cdot n}\); in ra giá trị \(H = (a_1 \cdot 22071997^1 + a_2 \cdot 22071997^2 + a_3 \cdot 22071997^3 + \dots + a_{2 \cdot n} \cdot 22071997^{2 \cdot n}) \mod (10^9 + 19972207)\).
  \end{itemize}

Ràng buộc

Bộ test của bài được chia làm các subtask như sau:

• Subtask \(1\) (\(12\) điểm): \(n \le 5\)
• Subtask \(2\) (\(20\) điểm): \(n \le 13\)
• Subtask \(3\) (\(20\) điểm): \(k = 1\)
• Subtask \(4\) (\(14\) điểm): \(\tau \le 233\) và \(n \le 377\)
• Subtask \(5\) (\(18\) điểm): \(n \le 4181\)
• Subtask \(6\) (\(16\) điểm): Không có ràng buộc gì thêm

Ví dụ

3
3 1
3 2
3 3

827482776
815013008
426921014

Giải thích

Trong bộ dữ liệu thứ nhất, hoán vị cần tìm là \((3,2,1,6,5,4)\). Giá trị cần in là \((3 \cdot 22071997^1 + 2 \cdot 22071997^2 + 1 \cdot 22071997^3 + 6 \cdot 22071997^4 + 5\cdot 22071997^5 + 4 \cdot 22071997^6) \mod (10^9 + 19972207)\\ = 462497922830663637557404222323368989234538169 \mod (10^9 + 19972207) = 827482776\)

Trong bộ dữ liệu thứ nhì, hoán vị cần tìm là \((4,2,1,6,5,3)\). Giá trị cần in là \((4 \cdot 22071997^1 + 2 \cdot 22071997^2 + 1 \cdot 22071997^3 + 6 \cdot 22071997^4 + 5 \cdot 22071997^5 + 3 \cdot 22071997^6) \mod (10^9 + 19972207)\\ = 346873448671141086341527499616207522877585437 \mod (10^9 + 19972207) = 815013008\)

Trong bộ dữ liệu thứ ba, hoán vị cần tìm là \((4,3,1,6,5,2)\). Giá trị cần in là \((4 \cdot 22071997^1 + 3 \cdot 22071997^2 + 1 \cdot 22071997^3 + 6\cdot 22071997^4 + 5 \cdot 22071997^5 + 2 \cdot 22071997^6) \mod (10^9 + 19972207)\\ = 231248974511618535125650776909533229550128717 \mod (10^9 + 19972207) = 426921014\)