#P18109. Native Niuean
Native Niuean
Native Niuean
对于一个非空的正整数数组 ,定义
$$f_0=f_1=1,\qquad f_i=a_{i-1}f_{i-1}+f_{i-2}\quad(i\ge2).$$该数组的 nativeness 定义为
如果一个数组的字典序严格小于它反转后的数组,就称它为 niuean 数组。
给定整数 ,求 nativeness 不超过 的 niuean 数组有多少个。数组长度可以是任意正整数,数组中的每个元素也可以是任意正整数。答案对 取模。
输入格式
输入一个整数 ,其中 。
输出格式
输出一个整数,表示所求数组数量对 取模的结果。
样例 1
输入:
6
输出:
1
样例 2
输入:
7
输出:
2
样例 3
输入:
13
输出:
8
样例 4
输入:
42
输出:
114
样例 5
输入:
67
输出:
305
样例 6
输入:
6767
输出:
3471737
样例 7
输入:
676767
输出:
863282261
样例 8
输入:
67676767
输出:
217404956
样例 9
输入:
6767676767
输出:
691869515