题目描述

长度为 $n$ 的信号序列中，每个位置放一个红色信号或蓝色信号。红色信号有 $r$ 种型号，蓝色信号有 $b$ 种型号。相邻两个位置不能都放红色信号。求合法序列数，答案对 $1000000007$ 取模。

输入格式

一行三个整数 $n,r,b$。

输出格式

输出合法序列数对 $1000000007$ 取模的结果。

样例

2 2 3

21

数据规模与约定

$1\le n\le10000000$，$1\le r,b\le1000000000$。同色不同型号视为不同选择。