Today is hidadz's birthday, and she has invited many friends to her birthday party.

hidadz brings her friends to the garden, intending to have them sit in a row to play a game. To ensure the game is not boring, the seating arrangement must satisfy the following condition:

For any contiguous segment, the absolute difference between the number of boys and the number of girls must not exceed $k$.

Soon, the children find one such arrangement and begin the game. hidadz's good friend Susie discovers that there are actually many such seating arrangements. Since they found one so quickly, they begin to wonder: exactly how many such arrangements are there? The math-loving hidadz and her friends start to ponder this question...

Assuming there are $n$ boys and $m$ girls at the party, can you answer Susie and hidadz's question? Since this number can be very large, they only want to know the remainder when this number is divided by $12345678$.

Input

The input contains a single line with three integers: the number of boys $n$, the number of girls $m$, and the constant $k$.

Output

The output should contain a single line representing the answer required by the problem.

Examples

Input 1

1 2 1

Output 1

1

Constraints

For 30% of the data, $n, m \le 20$; For 100% of the data, $n, m \le 150$, $k \le 20$.