4002 - FK

Created by V Copa UPR - Elio Alejandro Govea Aguilar
Added by eliogovea (2018-05-22)
Limits
Total Time: 60000 MS | Test Time: 2500 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

The first time Nerdson heard about the Fibonacci sequence (f (1) = 1, f (2) = 1, f (n) = f (n - 1) + f (n - 2)) he was amazed and dedicated several days to study some of its properties, after learning how to calculate them, he found an elegant way to calculate the sum of the first n numbers of the sequence, resulting quite easy, so he needed a bigger challenge. He thought that calculating such a sum by raising each element to the k would be just as easy, but it has not been like that, he still has no way of doing it. Nerdson is looking for someone to help him perform a program that calculates such sum given n and k, module 1000000007. Please help him.

La primera vez que Nerdson escuchó sobre la secuencia de Fibonacci (f(1) = 1, f(2) = 1, f(n) = f(n - 1) + f(n - 2)) quedó asombrado y dedicó varios días a estudiar algunas de sus propiedades, después de aprender a calcularlos, encontró una elegante forma de calcular la suma de los primeros n  números de la secuencia, resultándole bastante fácil, así que necesitaba un reto mayor. Pensó que calcular tal suma elevando cada elemento a la k  le resultaría igual de fácil, pero no ha sido así, todavía no tiene forma de hacerlo. Nerdson está buscando alguien que lo ayude a realizar un programa que calcule tal suma dados n  y k, modulo 1000000007. Por favor ayúdalo.

;jsessionid=5CF30F78B34CCE219E81EB09B2638791
The first time Nerdson heard about the Fibonacci sequence (f (1) = 1, f (2) = 1, f (n) = f (n - 1) + f (n - 2)) he was amazed and dedicated several days to study some of its properties, after learning how to calculate them, he found an elegant way to calculate the sum of the first n numbers of the sequence, resulting quite easy, so he needed a bigger challenge. He thought that calculating such a sum by raising each element to the k would be just as easy, but it has not been like that, he still has no way of doing it. Nerdson is looking for someone to help him perform a program that calculates such sum given n and k, module 1000000007. Please help him.

Input specification

A line with two numbers n (1 <= n <= 1e18), k (1 <= k <= 100).

Una línea con dos números n (1 <= n <= 1e18), k (1 <= k <= 100).

;jsessionid=5CF30F78B34CCE219E81EB09B2638791
A line with two numbers n (1 <= n <= 1e18), k (1 <= k <= 100).

Output specification

A line with an integer with the answer.
Una línea con un entero con la respuesta.
A line with two numbers n (1 <= n <= 1e18), k (1 <= k <= 100).

Sample input

3 2

Sample output

6

Hint(s)

The input example f(1) = 1, f(2) = 1, f(3) = 2, the answer is 1 + 1 + 4 = 6.
The input example f(1) = 1, f(2) = 1, f(3) = 2, the answer is 1 + 1 + 4 = 6.
The input example f(1) = 1, f(2) = 1, f(3) = 2, the answer is 1 + 1 + 4 = 6.