Problem Statement

Hamuko is going to try Gravity Glue.
Gravity Glue is an art form in which stones of various sizes are stacked high without using any adhesive.

Since Hamuko is captivated by fractals, she has decided to stack stones so that their sizes form a fractal.
The Gravity Glue $G_{b, d}$ is a way of stacking stones uniquely determined by its beauty $b>0$ and difficulty $d>0$.

The Gravity Glue $G_{1, d}$ of beauty $1$ is a stack of $d$ stones of size $1$ ($d$ is any positive integer).
The Gravity Glue $G_{i+1, d}$ of beauty $i+1$ uses $d$ stones of size $i+1$, stacked in the sandwich form
($G_{i, d}$, stone of size $i+1$, $G_{i, d}$, stone of size $i+1$, ..., stone of size $i+1$, $G_{i, d}$).

Now, Hamuko has finished building $G_{b, d}$ up to the $n$-th level from the bottom.
Find the total size of the stones needed to complete the rest, modulo $10^9+7$.

Input

n
b d

$0 \le n \le 10^9$, integer
$1 \le b \le 10^9$, integer
$1 \le d \le 10^9$, integer

It is guaranteed that $n$ does not exceed the height of $G_{b, d}$.

Output

Print a newline at the end.

Sample

0
3 1

11

4
3 1

4

7
3 1

0

4
3 2

31

114514
1919114 5141919

666638169