問題文

$N$ 頂点単純無向グラフ $G$ のうち、線グラフ $L(G)$ が自分自身と同型であるものの個数を、同型の違いを除いて、$10^9+7$ で割った余りを求めてください。

線グラフ $L(G)$ とは、次で定義されるグラフです。

• $V(L(G)) = E(G)$
• $E(L(G)) = \{\{a, b\} : a, b \in E(G), |a \cap b| = 1\}$

同型なグラフの例です。このような、接続関係が同じになる頂点の対応が存在するグラフ $G$ は同一視して数えてください。

入力

$N$

$1 \leq N \leq 1000$

出力

$N$ 頂点単純無向グラフ $G$ のうち、線グラフ $L(G)$ が自分自身と同型であるものの個数を、同型の違いを除いて、$10^9+7$ で割った余りを出力してください。 最後に改行してください。