J. Down the rabbit hole we go!
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ahmad is very tired, so he decided to play Minecraft with his friend Apraham.

As soon as he entered the game, a guy named Steve gave him $$$2$$$ fully grown rabbits and disappeared.

Apraham, curious about how rabbits live in this world, made some observations:

  • Every X days, a pair of fully grown rabbits spawns $$$8$$$ new baby rabbits.

  • These newly spawned baby rabbits are smaller and cannot spawn new rabbits.

  • After Y days, a baby rabbit grows up and becomes a fully grown rabbit. Once mature, it behaves like its parents and can start spawning new rabbits every X days.

Ahmad and Apraham now want to crash the server with these super cute rabbits UWU HeHe..

Today Ahmad has $$$2$$$ fully grown rabbits and he is so curious about how many rabbits will he have after n days.

As i said Ahmad is STILL tired so this mission is yours obviously :)

Since the final answer could be astronomically large, please output the result modulo $$$10^9+7$$$ .

Will you go down the rabbit hole?

Input

The only line contains three integers $$$n,X,Y \: (1 \le n\le 10^{18})$$$ $$$(1\le X,Y\le 1000)$$$

Output

Print a single integer , the number of rabbits Ahmad has after $$$n$$$ days mod $$$10^9+7$$$

Examples
Input
2 2 3
Output
10
Input
20 2 3
Output
8018
Input
1000 4 5
Output
641939610
Note

in the first test case:

after two days Ahmad will get extra 8 rabbits so 2+8=10