You are given a binary string str of length n.
A binary string consists of only '0' and '1'. 
For each subsequence(excluding empty) for string str, you need to find its decimal representation.
Print the number of distinct decimal values of the subsequences. 
Since, the answer can be very large, print it modulo (10^9 + 7).

Input - 
Line 1 contains number of test cases T.
Line 2 contains n - length of binary string str
Line 3 contains str - the binary string

Constraints -
n <= 2*(10^5)