Description

Today is hidadz’s birthday, and she has invited many friends to her birthday party. hidadz takes her friends to the garden, planning to sit in a row to play a game. To keep the game from being boring, the seating arrangement must satisfy the following condition:

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

Soon, the kids find one such arrangement and start the game. hidadz’s good friend Susie notices that there are actually many such seating arrangements, so since everyone can quickly find one, how many are there in total? The math-loving hidadz and her friends begin to think about this question.

Assume there are $n$ boys and $m$ girls at the party. Can you answer Susie and hidadz’s question? Since this number can be large, they only want the remainder when it is divided by $12345678$.

Input Format

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

Output Format

Output a single line containing the required answer.

1 2 1

1

Hint

For $30\%$ of the testdata, $n, m \le 20$.

For $100\%$ of the testdata, $n, m \le 150$, $k \le 20$.

Translated by ChatGPT 5