問題文

1 から N までの整数が書かれた、N 個のボールがあります。 k = 1, 2, 3, ..., N それぞれについて、以下の質問に答えてください。

• これら N 個のボールから 1 個以上のボールを選ぶ方法は 2^N-1 通り存在するが、その中で次の条件を満たす選び方は何通りあるか。
  • どの選んだ 2 つのボールについても、書かれている整数の差が k 以上である。
• ただし、答えは非常に大きくなることがあるので、10^9+7 で割った余りを出力すること。

制約

• 1 \leq N \leq 10^5
• N は整数

入力例 1

1

出力例 1

1

ボール 1 を選ぶ 1 通りのみが存在します。

入力例 2

2

出力例 2

3
2

k=1 のとき、選んだボールの集合として、\{1\}、\{2\}、\{1,2\} の 3 通りが存在します。

k=2 のとき、\{1\}、\{2\} の 2 通りが存在します。

入力例 3

3

出力例 3

7
4
3

入力例 4

4

出力例 4

15
7
5
4

入力例 5

7

出力例 5

127
33
18
13
10
8
7

入力例 6

20

出力例 6

1048575
17710
2744
906
430
250
167
118
90
75
65
56
48
41
35
30
26
23
21
20

入力例 7

50

出力例 7

898961330
951279874
262271567
14341526
1985602
466851
153365
63191
30623
16687
9987
6453
4354
3070
2290
1790
1427
1138
910
735
605
512
448
405
375
350
326
303
281
260
240
221
203
186
170
155
141
128
116
105
95
86
78
71
65
60
56
53
51
50

10^9+7 で割った余りを出力してください。