Subsets whose lexicographic order matches

Time limit8sMemory limit512 MB

Summary

Count non-empty subsets of the integers from A to B whose numeric order equals their lexicographic decimal order, modulo P.

Level: Hard8 of 10
Topics: Combinatorics, Dynamic programming, Trie, Math
Solved: No attempts yet

Problem

Consider sets of natural numbers. In some sets, sorting the elements by value and sorting their decimal representations lexicographically give the same order. {2, 27, 3125, 9000} is such a set. {2, 27, 243} is not, because lexicographic sorting gives {2, 243, 27}.

Take the set of all integers from $A$ to $B$ inclusive and count the subsets that have this property. The empty set is not counted. The count can grow very large, so print it modulo $P$ , which is given in the input.

Input

The input holds several datasets. Each dataset is one line with three integers $A$ , $B$ , and $P$ separated by a space. They satisfy $1 \le A \le 10^9$ , $0 \le B - A < 10^5$ , and $1 \le P \le 10^9$ .

A line holding three zeros marks the end of the input. Do not process that line.

Output

For each dataset, print the number of subsets modulo $P$ on its own line.

Examples3

Example 1

Input

1 10 1000
1 100000 1000000000
999999999 1000099998 1000000000
0 0 0

Expected output

513
899507743
941554688

Example 2
Input
```
5 5 1000
0 0 0
```
Expected output
```
1
```

Example 3

Input

1 2 1000000000
1 3 1000000000
9 11 1000000000
0 0 0

Expected output

3
7
4