General Highway Inspection#12828

General Highway Inspection

1 second
512 megabytes
Very hard

There are only three big cities in the Intland — Doublein, Longdon and Longlongdon.

There are bidirectional highways built between Doublein and Longdon, roads between Doublein and Longlongdon, and roads between Longdon and Longlongdon.

The Ministry of Transport of Intland is planning the General Highway Inspection. The inspectors are planning to start from Doublein, where the Ministry is placed, travel along each road exactly once, and return back to Doublein.

It is clear that the Ministry has many plans to choose from. They would like to find out the number of different plans, modulo (10^9+7).

Note that two plans and are considered different only if there exists an where the -th traveled road in plan is different from the -th road in plan .

Input

The first line of the input contains integers a, b, c (1 \leq a, b, c \leq 10^5).

Output

Print an integer that denotes the number of different ways modulo (10^9+7).

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading