問題一覧 > 通常問題

No.3777 Train Seats

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 46
作問者 : Rapca1256 / テスター : 👑 p-adic aogera tomorunn
お気に入りにしたユーザー ProblemId : 13842 / 自分の提出
問題文最終更新日: 2026-08-22 13:23:05
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 519 (順位表) の他の問題:

Problem Statement

$N$ chairs are lined up in a horizontal row. From now on, $N$ people will arrive in order, $1$ person at a time.
If there are $1$ or more chairs satisfying all of the following conditions, the newly arrived person chooses $1$ of them and sits on it.

  • No one is sitting on the chair.
  • There is no chair to its right, or no one is sitting on the chair to its right.
  • There is no chair to its left, or no one is sitting on the chair to its left.

If no chair satisfies the conditions, the person chooses $1$ chair on which no one is sitting yet and sits on it.

Find the total number of possible orders in which the chairs are sat on, modulo $998244353$.

Input

$N$

The input satisfies the following constraints.

  • All input values are integers.
  • $1 \le N \le 1000$

Output

Find the total number of possible orders in which the chairs are sat on, modulo $998244353$.
Print a newline at the end.

Sample

Sample 1
Input
3
Output
4

Let chair $i$ denote the $i$-th chair from the left, and let chair $S_i$ be the chair on which the $i$-th person sits. Then the possible sequences $S$ are as follows.

  • $(1, 3, 2)$
  • $(2, 1, 3)$
  • $(2, 3, 1)$
  • $(3, 1, 2)$
Sample 2
Input
1
Output
1

Sample 3
Input
7
Output
1008

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。