Hôm nay, các táo đang chuẩn bị cho trận đá bóng căng nhất lịch sử với các thiên đình khác. Các thành viên gồm: Táo kinh tế: dang7rickroll, táo y tế: phanhuykhang, táo mạng: nguyenminhhai021009, táo giao thông: stack_queue_4977, táo nông nghiệp: huyhau6a2, ...(Tên viết trong đây là hư cấu hehe)

Trước sự kiện này, ngọc hoàng đã tạo ra \(1\) thử thách để luyện tập cho các táo. Cụ thể như sau: sẽ có \(1\) con đường phân nhánh vô hạn, với nút đầu luôn có giá trị là \(1\). Các táo sẽ phải di chuyển đúng \(n\) bước, bước đầu tiên sẽ đi vào nút gốc, các bước sau có thể chọn \(L\) hoặc \(R\). Với \(L\): nút tiếp theo sẽ có giá trị nhân đôi lên so với nút trước đó, với \(R\): nút tiếp đó sẽ có giá trị nhân đôi lên cộng \(1\) so với nút trước đó. VD ta có đồ thị như sau:

                                                                            1
                                                                           / \     
                                                                          /   \     
                                                                         /     \     
                                                                    2(1.2=2)  3(1.2+1=3)

Số điểm bạn đạt được sẽ là nút cuối cùng bạn đang đứng sau \(n\) bước. Ngọc hoàng đang thắc mắc rằng tổng số điểm với tất cả các khả năng có thể xảy ra là bao nhiêu, do quá mệt mỏi sau \(1\) năm điều hành các táo nên ngọc hoàng quyết định nhờ táo mạng, nhưng chợt nhớ các bạn trên LQDOJ, với lại lười search mạng quá và còn phải tập luyện nên táo mạng xin nhờ các bạn hãy giải quyết thắc mắc của ngọc hoàng giúp nhé!

Input

• Dòng 1 gồm số \(q\) chỉ số truy vấn\((q\le 10^5)\)
• Sau đó là \(q\) dòng, mỗi dòng nhập duy nhất 1 số \(n(n\le 10^{18})\)

Output

• Mỗi truy vấn xuất duy nhất 1 số là kết quả của bài toán sau khi mod \(10^9+7\)

Example

3
1
3
123456

1
22
316875933