SUBSHARD - Subset and upset (HARD)

no tags 

The whole world is crazy about subset sum. We define subset sum as sum of all subparts. A subpart is a number which is obtained by erasing certain digits and arranging the remaining numbers in the same order. You have to calculate the subset sum of the given number. Since the number can be very large return the subset sum modulo m.

For example if the number is 1357, then the various subparts are 1, 3, 5, 7, 13, 15, 17, 35, 37, 57, 137, 135, 157, 357, 1357 .

Input

First line contains T(1 ≤ T ≤ 50) denoting the number of test cases.

Next T lines containing two numbers n(0 < n < 101000) and m(1 < m < 109).

Output

Print the subset sum modulo m.

Example

Input:
6
111 9
111 200
456 9
456 1000
1357 1000
1357 5000
Output:
3
147
6
618
333
2333

 

Time Limit ≈ 2*(My Python 3 Program Top Speed)

 

See also: Another problem added by Tjandra Satria Gunawan


hide comments
Rishabh Joshi: 2015-05-31 16:03:34

Can you please check my solution. O(n) getting TLE.
ID - 14362730
or ID - 14362674

Anmol Garg: 2014-06-30 14:59:03

My 50th. :D

gabber: 2012-12-25 16:42:50

Use MOD only where you need it!

R: 2012-12-11 09:57:38

@author
getting SIGABRT my code id is 8237489
plz help
similar code got ac in NITT5
Ans: Avoid integer division and modulo by zero

Last edit: 2012-12-11 11:22:19
♘Prabhat: 2012-10-12 02:10:15

@Tjandra can you please check my code(ID 7834532) why i'm getting this compilation error
/usr/lib/gcc/i486-linux-gnu/4.3.2/../../../../lib/crt1.o: In function `_start':
/home/aurel32/tmp/glibc/glibc-2.9/csu/../sysdeps/i386/elf/start.S:115: undefined reference to `main'
collect2: ld returned 1 exit status

:D: 2012-10-11 21:56:48

Yes :)

Alex Anderson: 2012-10-09 19:20:17

Just confirming, you guys meant O(log n) and O(log^2 n), right?

Problem Solver: 2012-10-08 15:11:56

Yeah, solved this problem, it's very nice, thanks.

Ehor Nechiporenko: 2012-10-04 11:49:46

So nice!!! What about codegolf challenge version of the problem?

Last edit: 2012-10-04 11:49:59
(Tjandra Satria Gunawan)(曾毅昆): 2012-10-04 11:10:46

I think 1 seconds time limit is the best setting ;-)
Congratulations for all that got AC :-)


Added by:Tjandra Satria Gunawan
Date:2012-10-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Hard version of NITT5 problem.