Balanced Seating Arrangements

Hidadz is celebrating her birthday and has invited many friends to her party. All the children (boys and girls) are going to sit in a row in the garden to play games. To make sure the game is interesting, they decide that for every contiguous segment of the seating, the difference between the number of boys and girls does not exceed a given integer k (in absolute value). In other words, if we denote by \(S_i\) the difference between the number of boys and girls among the first \(i\) children (with \(S_0 = 0\)), then for any indices \(0 \le i < j \le n+m\) the following must hold:

\[ |S_j - S_i| \le k \]

Given that there are n boys and m girls at the party, your task is to count the number of seating arrangements (where the children are considered identical by gender) that satisfy the above condition, and output the answer modulo \(12345678\). (Note that the seating order is a sequence consisting of exactly n occurrences of 'B' and m occurrences of 'G'.)

Input Format: Three integers n, m and k are given in a single line separated by spaces.

Output Format: Output a single integer, the number of valid seating arrangements modulo \(12345678\).

Example:

• For n=1, m=1, k=1, a valid arrangement can be either B G or G B. Hence, the answer is 2.
• For n=2, m=1, k=1, among the three possible sequences, only B G B satisfies the condition. Hence, the answer is 1.

inputFormat

The input consists of a single line containing three space-separated integers n, m, and k, where:

• n is the number of boys.
• m is the number of girls.
• k is the maximum allowed difference in the number of boys and girls for any contiguous segment.

outputFormat

Output a single integer: the number of valid seating arrangements modulo \(12345678\).

sample

1 1 1

2