Know your ABC's

Interview

Time limit2sMemory limit1024 MB

Summary

Count the strings with a A's, b B's, and c C's where no two adjacent letters match, modulo 10^9 + 7.

Level: Medium5 of 10
Topics: Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

UCF has started running a pre-school where it teaches all the students their ABCs. Every block the kids play with shows one of the letters A, B, or C. The kids like arranging the blocks, but they dislike any arrangement where two identical letters sit next to each other.

For example, if a kid has 2 A blocks, 3 B blocks, and 1 C block, BACBAB is a valid arrangement. CBABBA is not valid because the letter B appears twice in a row.

The teacher wants to know how many different valid orders the blocks can be arranged in. Two arrangements are different if they have a different letter in some position.

Input

A single line contains three integers $a$ , $b$ , and $c$ ( $1 \le a \le 100$ , $1 \le b \le 100$ , $1 \le c \le 100$ ), the number of blocks showing A, B, and C.

Output

Print the number of valid arrangements of all the blocks in a row, with no two consecutive blocks showing the same letter, modulo $10^9 + 7$ .

Examples2

Example 1
Input
```
2 3 1
```
Expected output
```
10
```
Example 2
Input
```
15 2 7
```
Expected output
```
0
```