斐波那契数列是一个非常有趣的数列，其定义如下：
用人话来说，就是一个序列，第一项和第二项是 ，从第三项开始，每一项都是他的前两项之和。
这样写出的斐波那契数列如下：
老师发明了一种加强版斐波那契数列，其定义如下：
公式难懂，用人话讲，就是斐波那契数列的每一项都是前 项之和，当然，如果前面不满 项，就取前面所有项的和。容易得出，不同的 会对应不同的数列。
你现在的任务是求出这个加强版斐波那契数列的第 项。由于数字可能很大，你需要将其对 取模。
9 3
81
