Count Palindromic Sequences

You are given three integers k, p and s. Your task is to count the number of palindromic sequences of length k consisting of non-negative integers strictly less than p whose sum equals s.

A sequence A = [a₁, a₂, ..., a_k] is considered palindromic if A[i] = A[k-i+1] for all valid i. In other words, the sequence reads the same backwards and forwards.

Input Example: For instance, if k = 3, p = 3 and s = 4, there are 2 valid palindromic sequences (namely [1,2,1] and [2,0,2]).

Note: It is guaranteed that the input values are small enough to allow a brute-force or recursive search solution.

inputFormat

The first and only line of input contains three integers k, p and s separated by spaces.

Constraints:

• 1 ≤ k ≤ 10 (or a small number that makes brute-force viable)
• 1 ≤ p ≤ 10
• 0 ≤ s ≤ 100

outputFormat

Output a single integer which is the number of k-length palindromic sequences of non-negative integers less than p that sum to s.

3 3 4

2