この問題を解きました。ネタバレを含むのでご注意ください。
見た瞬間にただのしゃくとり法だと思って実装したらサンプル2が通らなくて絶望しました。
問題はよく読みましょう（反省）
結局解答を見てACしてしまいましたが、あとから考えると気づきを得るポイントがあったのでそのへん書いておきます。
例えば以下のような入力があったと考えます。
4 5 3 3 3 3
この場合に数え上げることができるパターンは
1: 3 3 2: 3 3 3 3: 3 3 3 3 4: 3 3 5: 3 3 3 6: 3 3
この6パターンです。
ここで気が付きたいのが、パターン1の時点ですでにK(この場合は5)以上になっているので、パターン2とパターン3のために数えなおす必要はありません。
パターン4とパターン5の関係も同様です。
これに気が付くことができれば、しゃくとり法に少し手を加えてO(N)で答えを出すことができます。
こういう「〇〇が決まれば△△も自動的に決まる」みたいなやつは常に目を光らせておきたいですね（気がつけなくてくやしい）。
もうひとつ、ACまでに何度もWAを出して途方に暮れていたんですが、Kをintで受け取っていたことが原因でした... （Kは最大 1010なのでlong long
提出したコード
