Lucky Tickets

Time limit1sMemory limit128 MB

Summary

Count lucky n-digit numbers among k consecutive values starting at a uniformly random s in [a,b], and print the expected count as a fraction.

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

Problem

Egor works as a bus conductor. Every day he receives a pack of tickets to sell, and he always wonders how many of them are lucky, because he believes the more lucky tickets there are, the luckier his day will be.

Each ticket number consists of exactly $n$ digits, where $n$ is even. A ticket is lucky if the sum of its first $n/2$ digits equals the sum of its last $n/2$ digits.

The first ticket of the pack Egor receives is equally likely to be any integer from $a$ to $b$ inclusive (uniform distribution). A pack contains $k$ tickets with consecutive numbers: if the starting number is $s$ , the pack is $s, s+1, \dots, s+k-1$ .

Find the expected number of lucky tickets in tomorrow's pack.

Input

A single line with three integers $a$ , $b$ , and $k$ ( $0 \le a \le b < 10^{12}$ , $1 \le k \le 100000$ ).

$a$ and $b$ have the same number of digits, and this number equals the digit count $n$ of every ticket. Both values may have leading zeros, and the digit count is taken exactly as written. The number of digits in $a$ and $b$ is always even.

Output

Print the expected number of lucky tickets in the pack as an irreducible fraction on a single line. If the result is an integer, print just that integer with no slash.

Examples3

Example 1
Input
```
0123 4567 150
```
Expected output
```
6519/635
```
Example 2
Input
```
10 10 20
```
Expected output
```
2
```
Example 3
Input
```
4000 4999 11
```
Expected output
```
103/125
```