Al Bundy a plecat la serviciu, lăsându-i soţiei lui, Peg, cardul de cumpărături. PIN-ul este valoarea expresiei $E\left(n\right)=\sum _{k=1}^n(2\cdot {(a^2+b^2)}^{\frac{k}{2}}\cdot cos(k\cdot \alpha )),$unde $\alpha =arctg\left(\frac{a}{b}\right)$, iar n, a, b sunt numere naturale nenule.

Cerința

Să se afle valoarea expresiei $E\left(n\right)$, modulo 1.000.000.007.

Date de intrare

Fișierul de intrare al.in conține pe prima linie numerele n, a, b, separate prin spațiu.

Date de ieșire

Fișierul de ieșire al.out va conține pe prima linie valoarea expresiei $E\left(n\right)$, modulo 1.000.000.007.

Restricții și precizări

• 1 ≤ n ≤ 1012
• 1 ≤ a , b ≤ 20

Exemplu:

al.in

3 5 12

al.out

1918

Explicație

Dacă $\alpha =arctg\left(\frac{5}{12}\right)$, atunci $sin\left(\alpha \right)=\frac{5}{13}$ şi $cos\left(\alpha \right)=\frac{12}{13}$.
Avem $$\begin{gathered} E\left(3\right)=2\cdot 13\cdot cos\left(\alpha \right)+2\cdot {13}^2\cdot cos\left(2\alpha \right)+2\cdot {13}^3\cdot cos\left(3\alpha \right)= \\ 2\cdot 13\cdot \frac{12}{13}+2\cdot {13}^2\cdot (2\cdot co{s}^2\left(\alpha \right)-1)+2\cdot {13}^3\cdot (4\cdot co{s}^3\left(\alpha \right)-3\cdot cos\left(\alpha \right))=24+238+1656=1918 \end{gathered}$$ .