Sau khi xuất sắc dành hạng \(24\) trong kỳ thi IOI 2015, kẻ-mà-ai-cũng-biết-là-ai-đấy quyết định tổ chức một bữa tiệc trà sữa chiêu đãi hết thảy bạn bè gần xa bà con khối phố. Kẻ-mà-ai-cũng-biết-là-ai-đấy đi đến quán trà sữa "ruột" của cậu ta và dự định mua \(k\) ly trà sữa về để chiêu đãi mọi người.

Quán trà sữa này có bán \(n\) món trà sữa khác nhau, được đánh số từ \(1\) tới \(n\). Có một điều đặc biệt về cửa hàng này là giá của các món trà sữa sẽ thay đổi sau mỗi lần mua. Cụ thể, ban đầu, giá một ly trà sữa loại \(i\) là \(i\) đồng. Tuy nhiên, mỗi khi kẻ-mà-ai-cũng-biết-là-ai-đấy mua một ly của loại nào, giá của chính loại đó sẽ tăng gấp đôi cho lần mua tiếp theo.

Ví dụ, khi kẻ-mà-ai-cũng-biết-là-ai-đấy mua ly trà sữa loại \(i\) đầu tiên, giá của ly này là \(i\) đồng. Sau đó, ly loại \(i\) tiếp theo có giá là \(i \cdot 2\) đồng. Nếu kẻ-mà-ai-cũng-biết-là-ai-đấy lại mua thêm một ly loại \(i\) nữa, ly thứ ba sẽ có giá là \(i \cdot 4\) đồng, và cứ thế tiếp tục.

Vào năm 2015, số tiền thưởng dành cho huy chương vàng Olympic Tin học quốc tế còn khá nhỏ (chỉ là \(15\) triệu đồng so với \(55\) triệu đồng ở thời điểm hiện tại), vì vậy kẻ-mà-ai-cũng-biết-là-ai-đấy muốn chi số tiền nhỏ nhất có thể. Các bạn hãy giúp kẻ-mà-ai-cũng-biết-là-ai-đấy chọn ra \(k\) ly trà sữa với tổng giá tiền nhỏ nhất nhé.

Dữ liệu

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

• Dòng đầu tiên chứa một số nguyên \(\tau\) \((1 \le \tau \le 2^{19})\) là số bộ dữ liệu.
• \(\tau\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(n\) và \(k\) \((1 \le n, k \le 2^{60})\) mô tả một bộ dữ liệu.

Kết quả

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

• Với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên duy nhất là phần dư của tổng giá tiền nhỏ nhất của \(k\) ly trà sữa khi chia cho \(10^9 + 22071997\).

Ràng buộc

• Subtask \(1\) (\(10\) điểm): \(n, k \le 2^6\)
• Subtask \(2\) (\(20\) điểm): \(n \le 2^6\) và \(k \le 2^{14}\)
• Subtask \(3\) (\(25\) điểm): \(\tau \le 2^5\) và \(n \le 2^8\)
• Subtask \(4\) (\(25\) điểm): \(\tau \le 2^{13}\)
• Subtask \(5\) (\(20\) điểm): không có ràng buộc gì thêm.

Ví dụ

1
3 6

16