小红的好数组

题号：NC267001
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小红定义一个数组是好数组，当且仅当所有长度为 3 的连续子数组的元素和为偶数。
现在小红希望你求出，长度为 $n$ ，且所有元素均为不超过 $k$ 的正整数的好数组数量。
由于答案可能过大，请对 $10^9+7$ 取模。

两个正整数，用空格隔开。

一个整数，代表好数组的数量。

示例1

复制

3 2

复制

共有[1,1,2],[1,2,1],[2,1,1],[2,2,2]这四个好数组。