XDP's permutations

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

XDP本来想教大家A+B或者线段树II,但是由于他沟女忘记出题了,所以sweetzero代替他出题了,但是由于sweetzero是个学渣,还在苦学分数的约分,没有时间出题。不过sweetzeo最近听说XDP建立了很多题库,里面都是他出的神题。于是sweetzero hack进XDP的电脑,从XDP珍藏的神题题库里面偷来了一道题:问存在多少个长度为N的排列,使得对于任意一个位置,abs(i - p[i]) <= 1?请将结果 % 1000000007输出。

Input

约100000组数据,每组数据一个查询N(1 <= N <= 100000)

Output

对于每个N,输出有多少满足条件的排列 % 1000000007

Sample Input

1
2

Sample Output

1
2

Source

classical

Manager

Information
Solved Number37
Submit Number57
Problem Tags
dp
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel