3012：A Number from Yanghui Triangle

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

a_{n, 0} = 1 (n ≥ 0)
a_{n, n} = 1 (n ≥ 0)
a_{n, r} = a_{n − 1, r − 1} + a_{n − 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 log₁₀ a_{n, r} < k for all 0 ≤ r ≤ n. Here are some examples:

n	k	p
0	1	1
3	2	01030301
5	2	010510100501

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

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 ≤ 10⁹) in order.