Non‐Intersecting Chords on a Circle

Given a circle with n points labeled from 1 to n arranged in clockwise order, a chord is drawn by connecting any two distinct points with a straight line inside the circle. We wish to count the number of different ways to draw a set of chords (possibly none) so that no two chords intersect in the interior of the circle. Two configurations are considered different if they have a different number of chords or if there exists at least one point whose connected partner (if any) is different between the two configurations.

Your task is to compute the total number of such non‐intersecting chord configurations modulo \(2023\). In all test cases the input n will be given – note that one of the hidden cases will have n = 2023, but you should support any valid n (with 0 ≤ n ≤ 3000, say).

Hint: Let \(f(n)\) denote the number of valid chord configurations on n points. A recurrence for \(f(n)\) is

\[ f(0)=1,\quad f(1)=1,\quad f(n)=f(n-1)+\sum_{j=0}^{n-2}f(j)\,f(n-2-j)\quad (n\ge2), \]

and the answer is \(f(n)\bmod2023\).

inputFormat

The input consists of a single line containing an integer n (for example, 3, 4, or 2023). You need to compute the number of valid non‐intersecting chord configurations on a circle with n points, modulo 2023.

outputFormat

Output a single integer — the number of valid configurations modulo 2023.

sample

3

4