Pascal's triangle

Interview

Time limit1sMemory limit512 MB

Summary

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.

Level: Medium5 of 10
Topics: Array, Dynamic programming, Implementation, Simulation
Solved: No attempts yet

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 $R$ holds $R$ numbers.

Consider the equilateral triangle whose top vertex is the $C$ -th number of row $R$ and whose side contains $W$ numbers. Add up every number on the sides of that triangle and inside it. For example, when $R$ is 3, $C$ is 1 and $W$ 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) = 42$ .

Given $R$ , $C$ and $W$ , write a program that computes this sum.

Input

The first line contains the positive integers $R$ , $C$ and $W$ in this order, separated by single spaces. ( $2 \le R + W \le 30$ , $2 \le C + W \le 30$ , $1 \le W \le 29$ , $C \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 $C$ -th number of row $R$ and whose side contains $W$ numbers.

Examples1

Example 1
Input
```
3 1 4
```
Expected output
```
42
```