AT_arc143_f [ARC143F] Counting Subsets

[problemUrl]: https://atcoder.jp/contests/arc143/tasks/arc143_f 正の整数 $ N $ が与えられるので，次の条件を満たす$ \{1,2,\ldots,N\} $ の部分集合 $ S $ の個数を $ 998244353 $ で割ったあまりを求めてください． - $ N $ 以下の正の整数はすべて $ S $ のいくつかの相異なる要素の和として表せる．さらに，そのような表し方は高々 $ 2 $ 通りである．

入力は以下の形式で標準入力から与えられる． > $ N $

答えを出力せよ．

### 制約 - $ 1\ \leq\ N\ \leq\ 1500 $ ### Sample Explanation 1 $ \{1,2\} $ と $ \{1,2,3\} $ が条件を満たす部分集合です．