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

hide comments
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

Added by:adrian
Date:2004-07-31
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