XOR Subset Selection

JYY is fascinated by the properties of the XOR operation. He observed that for any two integers, their XOR is \(0\) if and only if they are equal. Now, he is curious about the following problem:

Given an integer \(N\), count the number of ways to choose \(N\) distinct integers from the range \([0, R-1]\) such that their XOR sum equals \(0\). Note that the order of selection does not matter.

The twist is that \(R\) is a very large number. It is represented in binary by a string obtained by repeating a given binary string \(S\) exactly \(K\) times. For example, if \(S = 101\) and \(K = 2\), then the binary representation of \(R\) is 101101 (i.e. \(R = 45\)).

Since the answer can be very large, output the result modulo \(10^9+7\).

inputFormat

The input consists of a single line containing three items separated by spaces:

• An integer \(N\): the number of distinct integers to choose.
• A binary string \(S\): the pattern used to form the binary representation of \(R\).
• An integer \(K\): the number of times \(S\) is repeated to form the binary representation of \(R\).

outputFormat

Output a single integer: the number of ways to choose \(N\) distinct integers from \([0, R-1]\) whose XOR sum is \(0\), taken modulo \(10^9+7\).

sample

1 101 2

1