問題一覧 > 通常問題

No.2883 K-powered Sum of Fibonacci

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 37
作問者 : Iroha_3856 / テスター : Rac tikuwa_ hiro1729
3 ProblemId : 11213 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-09-08 08:24:42

問題文

以下のように数列 F=(F1,F2,…)F = (F_1, F_2, \ldots) を定義します。

  • F1=1F_1 = 1
  • F2=1F_2 = 1
  • Fi=Fi−1+Fi−2 (i≥3)F_i = F_{i-1} + F_{i-2}\ (i \geq 3)

正整数 N,KN, K が与えられます。

(∑i=1NFi K) mod 998244353\displaystyle \left( \sum_{i=1}^N F_i^{\ K} \right) \bmod 998244353 を求めてください。

入力

N KN\ K

入力は全て以下の制約を満たす

  • 1≤N≤10181 \leq N \leq 10^{18}
  • 1≤K≤1001 \leq K \leq 100
  • N,KN, K は整数

出力

答えを出力し、最後に改行してください。

サンプル

サンプル1
入力
4 3
出力
37

F1=1,F2=1,F3=2,F4=3F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3 となるので、答えは (13+13+23+33) mod 998244353=37(1^3 + 1^3 + 2^3 + 3^3) \bmod 998244353 = 37 となります。

サンプル2
入力
1 1
出力
1

N=1N = 1 もしくは K=1K = 1 となることもあります。

サンプル3
入力
1000000000000000000 100
出力
741845682

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。