Consider sets of natural numbers. Some sets can be sorted in the same order numerically
and lexicographically. {2,27,3125,9000} is one example of such sets; {2,27,243} is not since
lexicographic sorting would yield {2,243,27}.
Your task is to write a program that, for the set of integers in a given range A,B, counts the number of non-empty subsets satisfying the above property. Since
the resulting number is expected to be very huge, your program should output the number in
modulo P given as the input.
The input consists of multiple datasets. Each dataset consists of a line with three integers A,
B, and P separated by a space. These numbers satisfy the following conditions: 1 <= A <= 1,000,000,000, 0 <= B - A < 100,000, 1 <= P <= 1,000,000,000.
The end of input is indicated by a line with three zeros.
For each dataset, output the number of the subsets in modulo P .
1 10 1000 1 100000 1000000000 999999999 1000099998 1000000000 0 0 0
513 899507743 941554688
Migrated from old NTUJ.
JAG 模擬地区予選
| No. | Testdata Range | Score |
|---|