Blue Leap Robot

Little Blue has created a robot named Blue Leap because it primarily moves by hopping. Blue Leap can move forward by hopping and can also reverse its direction (make a turn). In each hop, the robot must jump an integer distance and it cannot jump more than \(k\) units at a time.

However, due to its unstable balance design, if Blue Leap makes two consecutive hops in which both hops have a distance of at least \(p\), it will fall. To avoid this, any sequence of hops must ensure that there are no two adjacent hops where both have a length \(\ge p\).

Little Blue is tasked with showcasing Blue Leap on a stage of length \(L\). To do this, Blue Leap will start at one end of the stage and hop to the other end. During a single journey from one side to the other, Blue Leap records the distance of each hop. Thus, a journey is represented by a sequence of positive integers where each integer is at most \(k\) and the sum of the sequence is exactly \(L\). Two journeys are considered different if their sequences differ in length or in any position.

Your task is to compute the number of distinct hop sequences (i.e. ways) for Blue Leap to go from one side of the stage to the other without falling (i.e. without having two consecutive hops both of length \(\ge p\)).

Note: The input consists of three integers \(L\), \(k\), and \(p\), separated by spaces.

All formulas are formatted in \(\LaTeX\): For each hop \(d\), we have \(1 \le d \le k\), and for any two consecutive hops \(d_i\) and \(d_{i+1}\), it cannot be that \(d_i \ge p\) and \(d_{i+1} \ge p\) simultaneously. Also, \(\sum d_i = L\).

inputFormat

The input consists of a single line containing three space-separated integers: \(L\) (the length of the stage), \(k\) (the maximum jump length per hop), and \(p\) (the threshold for a jump to be considered long, which may cause the robot to fall if two such jumps occur consecutively).

outputFormat

Output a single integer that represents the number of valid hop sequences that allow Blue Leap to go from one side of the stage to the other without falling.

sample

3 2 2

3