Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
A Number from Yanghui Triangle
Time Limit: 2000MSMemory Limit: 131072K
Total Submissions: 2316Accepted: 963

Description

Yanghui Triangle, as known as Pascal’s Triangle, is a number triangle with numbers arranged in staggered row such that

an, 0 = 1 (n ≥ 0)
an, n = 1 (n ≥ 0)
an, r = an − 1, r − 1 + an − 1, r (0 < r < n)

Consider a decimal number p with sequentially consists of k-digit decimal representations of the numbers in the n-th row of Yanghui Triangle where log10 an, r < k for all 0 ≤ rn. Here are some examples:

nkp
011
3201030301
52010510100501

The numerical value of p can be very large. Your task is to calculate p mod m for some integer m.

Input

The input consists of T test cases. The number of test cases T is given in the first line of the input file. Each test case consists of one line containing n, k, m (0 ≤ n ≤ 1 000 000, 1 ≤ k ≤ 1 000 000, 2 ≤ m ≤ 109) in order.

Output

The output should contain p mod m, one per line.

Sample Input

3
0 2 7
2 2 12345
5 2 1000000

Sample Output

1
10201 
100501

Hint

Use faster I/O to deal with the large-size input.

Source

POJ Monthly--2006.09.29, Kim, Chan Min (kcm1700@POJ)

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator