İkilik hasilatlar#2947
Sizə ədədindən ibarət bir sıra verilib. Bu ədədlərin arasına bir və ya daha çox vurma işarəsi daxil etməyin bütün mümkün yollarını nəzərdən keçirin ki, alınan ifadə düzgün olsun (vurmanın işarələri ardıcıl, sıra başında və ya sonunda ola bilməz). Məsələn, n = 4 üçün yol var: 1\times111, 11\times11, 111\times1, 1\times1\times11, 1\times11\times1, 11\times1\times1 və 1\times1\times1\times1. İfadələrin hasilatlarının cəmini hesablayın, ədədlərin ikilik sistemdə yazıldığını nəzərə alaraq: 1_2\times111_2 + 11_2\times11_2 + 111_2\times1_2 + 1_2\times1_2\times11_2 + 1_2\times11_2\times1_2 + 11_2\times1_2\times1_2 + 1_2\times1_2\times1_2\times1_2 = 33.
Siz bu cəmi istənilən üçün hesablamalısınız.
Birinci sətirdə (1 \le T \le 1000) — testlərin sayı. Sonrakı sətrin hər birində bir ədəd (2 \le n \le 10^9) verilir.
Hər bir üçün cavabı modulu üzrə çap edin.
Nümunə 1