School Days

Limits: 3 sec., 512 MiB

This statement was translated automatically from Ukrainian.

While working with foreign clients, Zenik remembered his school days when his English teacher gave him the following homework assignment:

• write the letter a \(cnt_a\) times,

• write the letter b \(cnt_b\) times,

• write the letter c \(cnt_c\) times.

Reminiscing about school, Zenik also remembered algebra lessons, where he once invented the following multiplication operation \(*\), which works only with the English letters a, b, and c: the product of two different letters gives the third remaining letter, and the product of identical ones gives the same letter. For example, \(a * a = a\), and \(b * c = c * b = a\).

Zenik decided to do his English homework again, but make it slightly more complicated with algebra. So, he writes out all the required letters in a certain order, thus forming a string of length \(cnt_a + cnt_b + cnt_c\). Note that the letters can be written out in any order.

For the resulting string, Zenik started to calculate the sequential product of all its characters. Sequential product is the product of all letters, where multiplication is performed sequentially from left to right. The product of the first two letters of the string results in one letter, which we multiply by the third letter, the result of this in turn by the fourth, and so on.

Zenik became curious about how many different strings he could write such that as a result of sequential multiplication he gets the letter \(c\). Written strings are considered different if and only if there exists a position at which they contain different characters. Zenik is worried that the number of different strings might be so large that he won’t even understand what kind of number it is, so he asks you to calculate this count modulo the prime number \(10^9 + 7\). And remember, changing the order of factors does change the sequential product!

Input

The first line gives three integers \(cnt_a\), \(cnt_b\), and \(cnt_c\) — the number of corresponding characters in the string.

Output

Output a single integer — the remainder of dividing the number of different desired strings by the prime module \(10^9 + 7\).

Constraints

\(1 \le cnt_a + cnt_b + cnt_c \le 10^3\).

Scoring consists of the following subtasks:

• 1 point for each example from the statement,

• 7 points: \(cnt_a = cnt_b = 0\),

• 8 points: \(cnt_a + cnt_b + cnt_c \le 9\),

• 24 points: \(cnt_a, cnt_b, cnt_c \le 30\),

• 33 points: \(cnt_a, cnt_b \le 74, cnt_c = 0\),

• 17 points: \(cnt_a, cnt_b, cnt_c \le 74\),

• 10 points: no additional constraints.

You will receive points for a subtask only if your program passes all tests in that subtask.

Samples

Input (stdin) сopy	Output (stdout) сopy
2 1 1	3

Notes

In the first example, only three strings acba, aabc, and caba are valid, because:

\(a * c * b * a = b * b * a = b * a = c\),

\(a * a * b * c = a * b * c = c * c = c\),

\(c * a * b * a = b * b * a = b * a = c\).