Alice and Bobo are playing a game on a graph with n vertices numbered with .
The vertex numbered with i is associated with weight .

The game is played as follows.
Firstly, Alice chooses a (possibly empty) subset of the edges.
Subsequently Bobo chooses a (possibly empty) subset of the n vertices to *cover* the edges chosen by Alice.
An edge is *covered* if one of its two ends is chosen by Bobo.
As Bobo is smart, he will choose a subset of vertices whose sum of weights, denoted as S, is minimum.

Alice would like to know the number of subsets of edges where Bobo will choose a subset whose sum of weights is exactly k (i.e. S = k), modulo .

The input consists of several test cases and is terminated by end-of-file.

Each test case contains two integers n and k.
For convenience, the number k is given in its binary notation.

For each test case, print an integer which denotes the result.

3 1
4 101
10 101010101

3
12
239344570

* 
* 
* The sum of n does not exceed 250,000.