广义肥波那契数列，以递归的方法定义如下： 例如，当时，数列为。 现在，请求出。
输入共一行,包含个正整数。
输出共一行，包含一个非负整数表示答案。由于结果可能较大，你只需要输出答案对取模的结果。
1 1 2 4
8
个正整数)
。
取模的结果。