Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P155PROA - ROUND 5A - Dãy số Fibonacci 1

Như ta đã biết dãy Fibonacci Fn  được định nghĩa như sau:

-          F1 = F2 = 1

-          Fn = Fn-1 + Fn-2  với n > 2.

Dãy số nguyên {an}= { a1, a2, … an } được gọi là dãy tỉ lệ của Fnếu ta có:

a[1]/F[1] = a[2]/F[2] = ... = a[n]/F[n]

Cho a1 và n, hãy tính tổng tất cả các phần tử của dãy {an}, kết quả được lấy dư cho 1000000007.

Input

Một dòng duy nhất chứa 2 số a1 và n (0 < a1, n <= 10^15).

Output

In ra một số nguyên duy nhất là đáp số của bài toán.

Example

Input:
3 5

Output:
36

Được gửi lên bởi:adm
Ngày:2015-03-30
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2022-08-11 07:10:00
trâu cũng AC
2019-08-01 18:39:01
Tham Khao Code C# Tai: https://ideone.com/SqRK69
2019-08-01 18:34:24
Tham Khao Code Tai: https://ideone.com/wUWVWx
2017-03-16 18:49:12


Last edit: 2017-03-16 18:50:48
2017-02-28 03:42:04
nhìn giới hạn n <= 10^15 mà muốn cạn lời -_-
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.