SCALES  Balancing the Stone
You are given scales for weighing loads. On the left side lies a single stone of known weight W<2^{N}. You own a set of N different weights, weighing 1, 2, 4, ..., 2^{N1} 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 5Warning: large Input/Output data, be careful with certain languages
hide comments
kshubham02:
20171006 10:29:00
For first case, on right side weight 1000 (=8) is already present.


orion_pax:
20170529 10:00:30
In first sample input how output is 3, there can be 4 cases L1 R1, L1+1 R2, L1+1+2 R4, L1+1+2+4 R8,, please help 

surya2196:
20161105 19:06:14
please explain test case 1


mahmood_2000:
20160828 20:43:58
use iteratve DP watch out for mod and make sure that the array size is big enough


fire_heart:
20160825 12:07:52
unexpected AC in 1 go :) good problem (y) 

Ghost Of Perdition:
20140124 02:21:35
Totally Awesome Problem !! 

SAVY:
20130820 04:31:48
Last edit: 20130820 13:22:21 
Added by:  adrian 
Date:  20040731 
Time limit:  7s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  based on a problem from the VII Polish Collegiate Team Programming Contest (AMPPZ), 2002 