E. Өөр нэг тоон дараалал

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Хүн бүр Фибоначчи дараалал гэж юу болхыг мэддэг. Энэ дараалал нь давтамжуудыг холбоотойгоор тодорхойлсон байдаг:

$F_{1} = 1, F_{2} = 2, F_{i} = F_{i - 1} + F_{i - 2} (i > 2).$

Бид шинэ тоонуудтай дараал $A_{i}(k)$-г дараах томъёогоор тодорхойлно:

$A_{i}(k) = F_{i} × i^{k} (i ≥ 1).$

Энэ асуудлын хувьд таны зорилго нь дараах нийлбэрийг тооцоолох явдал юм: $A_{1}(k) + A_{2}(k) + ... + A_{n}(k)$. Хариулт нь маш их тоо байж болох учраас модуляр $1000000007$ $(10^{9} + 7)$ гэж хэвлэнэ.

Оролт

Эхний мөрөнд зайгаар тусгаарлан хоёр бүхэл $n$, $k$ $(1 ≤ n ≤ 10^{17}; 1 ≤ k ≤ 40)$ тоонуудыг оруулна.

Гаралт

Эхэнд оруулсан $n$ элементүүдтэй $A_{i}(k)$ дарааллын нийлбэрийн үр дүнг хэвлэнэ. Энэ тоо нь модуляр $1000000007$ $(10^{9} + 7)$ байна.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
1 1
Гаралт
1
Оролт
4 1
Гаралт
34
Оролт
5 2
Гаралт
316
Оролт
7 4
Гаралт
73825
Сэтгэгдлүүдийг ачааллаж байна...