Cerința

Dorel tocmai a aflat despre existenţa şirului lui Fibonacci: F₀=0, F₁=1, F₂=1, F₃=2, F₄=3, F₅=5,… . Pentru numerele n, k şi p date, Dorel vă roagă să calculaţi suma F_p + F_k+p + F_2•k+p + … + F_n•k+p.

Date de intrare

Programul citește de la tastatură numerele n , k şi p.

Date de ieșire

Programul va afișa pe ecran suma cerută, modulo 1.000.000.007.

Restricții și precizări

• 1 ≤ n ≤ 1016
• 0 ≤ p < k ≤ 100

Exemplu:

Intrare

3 3 1

Ieșire

72

Explicație

Suma cerută este F₁ + F₄ + F₇ + F₁₀ = 1 + 3 + 13 + 55 = 72.