General Highway Inspection#12828

General Highway Inspection

1 секунда
512 мегабайтів
Дуже складна

У Intland є тільки три великих міста — Doublein, Longdon та Longlongdon.

Існує двонаправлених магістралей між Doublein та Longdon, — між Doublein та Longlongdon, та — між Longdon та Longlongdon.

Міністерство транспорту Intland планує Глобальну Інспекцію магістралей. Інспектори планують почати у Doublein, де розташовано міністерство, проїхати по кожній дорозі рівно один раз, та повернутись назад у Doublein.

Очевидно, що існує багато планів подорожі. Вони хочуть знайти кількість різних планів за модулем (10^9+7).

Два плани та вважаються різними тільки якщо існує де -та дорога у плані відрізняється від -ї дороги у плані .

Вхідні дані

Перший рядок входу містить цілих числа a, b, c (1 \leq a, b, c \leq 10^5).

Вихідні дані

Виведіть єдине ціле число — кількість різних планів за модулем (10^9+7).

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading