SCALES - Balancing the Stone

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

Input:
2
6 4 6
1000
6 6 100
100110

Output:
3
5
Warning: large Input/Output data, be careful with certain languages

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

hide comments
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 + 8 (Total 32==32)
There are no other ways.

Last edit: 2020-12-30 13:57:13
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
2016-11-05 19:06:14
please explain test case 1
2016-08-28 20:43:58
use iteratve DP watch out for mod and make sure that the array size is big enough
2016-08-25 12:07:52
unexpected AC in 1 go :) good problem (y)
2014-01-24 02:21:35 Ghost Of Perdition
Totally Awesome Problem !!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.