008 - ゲームブック

問題

ゲームブックとは、読者の選択によって指定されたページへ移動することで、物語を楽しめる本である。たとえば、本の5ページ目に、ページ番号8、17、32が書かれていれば、読者はこれらの中から１つ選択して、5ページ目から8、17、32ページ目のいずれかへ飛ぶことができる。

あなたは$N$ページのゲームブックを作成しようとしている。各ページにはいくつかのページ番号を書き込む。以下の条件をすべて満たすページ番号の書き方は何通りあるだろうか？

• 各ページには、そのページ番号よりも大きいページ番号を書き込む。
• 1ページ目から、直接またはいくつかのページを経由して、任意のページにたどり着ける。
• 任意のページから、直接またはいくつかのページを経由して、$N$ページ目にたどり着ける。

ゲームブックのページ数が与えられる。上の条件を満たすページ番号の書き込み方が何通りあるかを求めるプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$

１行にページの数$N$ ($2 \leq N \leq 500$)が与えられる。

出力

ページ番号の書き込み方が何通りあるかを表す数を998,244,353で割った余りを１行に出力する。

入出力例

入力例１

3

出力例１

2

入力例２

5

出力例２

122