melc

O armată de melci și-a propus să asedieze o cetate.

Cum melcii nu au vederea prea bună, aceștia urcă doar in timpul zilei. Dacă într-o zi coeficientul de încredere $A_i$ este impar, melcul va urca cu $B_i$ metri. Altfel, va lua o bună meritată pauză. În fiecare noapte, $A_i$ se împarte la $2$, iar $B_i$ se înmulțește cu 2 (melcul este atât de impresionat de curajul camarazilor săi încât își dublează forțele, dar nu va putea menține acest ritm).

Va continua să urce până când coeficientul lui de încredere în succesul asediului, $A_i$, ajunge să fie zero.

Să se afle la ce înălțime a ajuns fiecare melc. Cum aceasta poate fi foarte mare, se va afișa modulo $10^9+7$.

Date de intrare

Pe prima linie a fișierului melc.in se află $N$.
Următoarele $N$ linii conțin câte două numere $A_i$ și $B_i$, separate prin spațiu.

Date de ieșire

Să se afișeze în melc.out $N$ numere separate prin spațiu, corespunzătoare melcilor din intrare.

Restricții și precizări

• $1 \le N \le 3\cdot 10^5$;
• $1 \le A_i, B_i \le 10^{18}$;
• Rezultatele se afișează modulo $10^9 + 7$;
• Notă: Este posibil ca o sursa să obțină punctaj diferit aici față de în concurs.

Exemplu

melc.in

2
123 679123565
45564986 65455555

melc.out

532197914 426319863

Explicații

Pentru primul melc, $A_1$ și $B_1$ vor lua, pe parcursul zilelor, următoarele valori:

• $A_1 = 123$ și $B_1 = 679123565$ -- cum $A_1$ este impar, melcul va avansa 679123565 de metri (este foarte rapid și hotărât să ajungă sus, iar din ceva motiv zidurile sunt foarte înalte)
• $A_1 = 61$ și $B_1 = 1358247130$ -- melcul va urca 1358247130 de metri
• $A_1 = 30$ și $B_1 = 2716494260$
• $A_1 = 15$ și $B_1 = 5432988520$ -- melcul urcă încă 5432988520 de metri
• $A_1 = 7$ și $B_1 = 10865977040$ -- melcul mai urcă 10865977040 de metri
• $A_1 = 3$ și $B_1 = 21731954080$ -- încă 21731954080 de metri urcați
• $A_1 = 1$ și $B_1 = 43463908160$ -- un avans de încă 43463908160 de metri
• $A_1 = 0$ și $B_1 = 86927816320$

După 7 zile de urcat, melcul nostru vitezoman și-a pierdut motivația de a mai cuceri cetatea.

A urcat un total de 83532198495 de metri (mai mult de 83 de milioane de kilometri, jumătătea distanței de la Pământ la Soare), dar cum este o valoare care ne dă batăi de cap și doar să îi numărăm cifrele, vom afișa rezultatul modulo $10^9+7$, deci 532197914.