## SCALES - Balancing the Stone

no tags

You are given scales for weighing loads. On the left side lies a single stone of known weight W<2N. You own a set of N different weights, weighing 1, 2, 4, ..., 2N-1 units of mass respectively. Determine how many possible ways there are of placing some weights on the sides of the scales, so as to balance them (put them in a state of equilibrium). Output this value modulo a small integer D.

### Input

The input begins with the integer t, the number of test cases. Then t test cases follow.

For each test case, the first line contains three integers: N L D, where N denotes the number of weights at your disposal, L is the length of the binary representation of number W, and D is the modulus (1<= L<= N<= 1000000, 2<= D<=100). The second line contains the value of W, encoded in the binary system as a sequence of exactly L characters 0 or 1 without separating spaces.

### Output

For each test case, output a single line containing one integer - the calculated number of possible weight placements, modulo D.

### Example

```Sample input:
2
6 4 6
1000
6 6 100
100110

Sample output:
3
5
```
Warning: large Input/Output data, be careful with certain languages kshubham02: 2017-10-06 10:29:00 For first case, on right side weight 1000 (=8) is already present. Ways to balance (put these weights in the corresponding plates)- 1. Lt - 8, Rt - 0 (Total 8==8) 2. Lt - 16, Rt - 8 (Total 16==16) 3. Lt - 32, Rt - 16 (Total 32==32) There are no other ways. orion_pax: 2017-05-29 10:00:30 In first sample input how output is 3, there can be 4 cases L-1 R-1, L-1+1 R-2, L-1+1+2 R-4, L-1+1+2+4 R-8,, please help surya2196: 2016-11-05 19:06:14 please explain test case 1 mahmood_2000: 2016-08-28 20:43:58 use iteratve DP watch out for mod and make sure that the array size is big enough fire_heart: 2016-08-25 12:07:52 unexpected AC in 1 go :) good problem (y) Ghost Of Perdition: 2014-01-24 02:21:35 Totally Awesome Problem !! SAVY: 2013-08-20 04:31:48 Last edit: 2013-08-20 13:22:21