Pascal's triangle

Build Pascal's triangle and sum all entries inside the equilateral sub-triangle whose top cell is row R, position C, with side length W.

Medium5ArrayDynamic programmingImplementationSimulationInterviewNo attempts yetTime limit1sMemory limit512 MB

Problem

Pascal's triangle has the shape drawn below. The top cell holds 1, and every number except the two at the ends of a row is the sum of the number immediately above it on the left and the number immediately above it on the right. Both numbers at the ends of a row are 1.

Rows are numbered from the top starting at 1, and within a row the numbers are counted from the left starting at 1, so row RR holds RR numbers.

Consider the equilateral triangle whose top vertex is the CC-th number of row RR and whose side contains WW numbers. Add up every number on the sides of that triangle and inside it. For example, when RR is 3, CC is 1 and WW is 4, the shaded part of the picture above is that triangle, and the sum is 1+(1+3)+(1+4+6)+(1+5+10+10)=421 + (1 + 3) + (1 + 4 + 6) + (1 + 5 + 10 + 10) = 42.

Given RR, CC and WW, write a program that computes this sum.

Input

The first line contains the positive integers RR, CC and WW in this order, separated by single spaces. (2R+W302 \le R + W \le 30, 2C+W302 \le C + W \le 30, 1W291 \le W \le 29, CRC \le R)

Output

Print on the first line the sum of the numbers on the sides of and inside the equilateral triangle whose top vertex is the CC-th number of row RR and whose side contains WW numbers.