問題文

$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\le N\le 1000$

出力

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