Number Sorting#3599
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 (i.e. between and inclusive), 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 given as the input.
The input consists of multiple datasets. Each dataset consists of a line with three integers , , and separated by a space. These numbers satisfy the following conditions: 1 \le A \le 1000000000, 0 \le B-A < 100000, 1 \le P \le 1000000000.
The end of input is indicated by a line with three zeros.
For each dataset, output the number of the subsets in modulo .
Example 1