It's Nate's first day in High School, and he's really nervous! Nate hopes that High School will be great, full of antics and wacky adventures, field trips and tournaments, beach episodes and kawaii demons, just like what he's seen on anime (which he's sure is a realistic and not-at-all romanticized portrayal of High School). Most of all, he hopes to find his _nakama_.
Whatever a _nakama_ is, in Nate's High School class, there can be one or more _nakama_s, depending on the friendships within the class. Two students in the class can either be friends, or not be friends. Friendship is mutual: if student $A$ is friends with student $B$, then student $B$ is also friends with student $A$. Two students are part of the same _nakama_ if they are friends. If a student is not friends with anyone else in the class, they also count as one _nakama_.
The *nakama rating* of a class is the number of distinct _nakama_ present in the class.
Nate uses the timeline powers he got from watching Steins;Gate to examine *every possible way the people in his class could be friends with one another*. Two timelines are considered different if there exists at least one pair of students who are friends in one timeline and not friends in the other. What is the sum of the _nakama_ ratings of a class of $n$ students across all possible different timelines?
The input consists of a line with a single integer $n$, the number of students in the class.
*Constraints*
$1 <= n <= 3000$
Output a single integer, the sum of all the _nakama_ ratings of a class with $n$ students across all possible different timelines. Since the answer can get quite large, output its positive remainder when it is divided by $10^9 + 7$, a prime number.
Suppose there are $N = 3$ students in the class: Nate, Ayumi, and Jotaro. Illustrated below are all $8$ possible ways the class could be friends, and the _nakama_ rating of each possibility.
In case (a), there are no friendships between anyone in the class, so each student counts as one _nakama_. Therefore, the _nakama_ rating for this possibility is $3$.
In cases (b), (c), and (d), two of the students in the class are friends with each other, forming one _nakama_. The remaining student, who isn't friends with anyone, counts as another _nakama_. Therefore, the _nakama_ rating for each of these possibilities is $2$.
In cases (e), (f), (g) and (h), all of the students belong to the same _nakama_, so the _nakama_ rating for each of these possibilities is $1$. For example, in case (e), since Nate and Ayumi are friends, they belong to the same _nakama_. Since Nate and Jotaro are also friends, they also belong to the same _nakama_, hence Ayumi and Jotaro also belong to the same _nakama_.
The sum of the _Nakama_ Ratings across all $8$ possibilities is $3 + 2 + 2 + 2 + 1 + 1 + 1 + 1 = 13$.
Translator's Note: What is a _nakama_? Well, it's a really deep word that means a group of closest friends (like in One Piece) and there really is no English equivalent to how powerful that word is, so Nate has decided to keep it untranslated. The untranslated definition of _nakama_ is: 仲間 — 1. 一緒に物事をする間柄。また、その人。2.地位・職業などの同じ人々。3. 同じ種類のもの。同類。4. 近世、商工業者の同業組合。官許を得たものを株仲間といった。(デジタル大辞泉（小学館）より). You do not need to understand this definition to solve this problem.
## Input
The input consists of a line with a single integer $n$, the number of students in the class.*Constraints*$1 <= n <= 3000$
## Output
Output a single integer, the sum of all the _nakama_ ratings of a class with $n$ students across all possible different timelines. Since the answer can get quite large, output its positive remainder when it is divided by $10^9 + 7$, a prime number.
[samples]
## Note
Suppose there are $N = 3$ students in the class: Nate, Ayumi, and Jotaro. Illustrated below are all $8$ possible ways the class could be friends, and the _nakama_ rating of each possibility.In case (a), there are no friendships between anyone in the class, so each student counts as one _nakama_. Therefore, the _nakama_ rating for this possibility is $3$.In cases (b), (c), and (d), two of the students in the class are friends with each other, forming one _nakama_. The remaining student, who isn't friends with anyone, counts as another _nakama_. Therefore, the _nakama_ rating for each of these possibilities is $2$.In cases (e), (f), (g) and (h), all of the students belong to the same _nakama_, so the _nakama_ rating for each of these possibilities is $1$. For example, in case (e), since Nate and Ayumi are friends, they belong to the same _nakama_. Since Nate and Jotaro are also friends, they also belong to the same _nakama_, hence Ayumi and Jotaro also belong to the same _nakama_.The sum of the _Nakama_ Ratings across all $8$ possibilities is $3 + 2 + 2 + 2 + 1 + 1 + 1 + 1 = 13$.Translator's Note: What is a _nakama_? Well, it's a really deep word that means a group of closest friends (like in One Piece) and there really is no English equivalent to how powerful that word is, so Nate has decided to keep it untranslated. The untranslated definition of _nakama_ is: 仲間 — 1. 一緒に物事をする間柄。また、その人。2.地位・職業などの同じ人々。3. 同じ種類のもの。同類。4. 近世、商工業者の同業組合。官許を得たものを株仲間といった。(デジタル大辞泉（小学館）より). You do not need to understand this definition to solve this problem.
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ denote the initial height and number of stacks, respectively.
Let $ C \in \{A, B, C, D, E, F, X, Y\}^{n \times m} $ be the initial coin grid, where:
- $ A, B, C, D, E, F $ correspond to denominations $ \{1, 5, 10, 50, 100, 500\} $ (ordinary coins),
- $ X, Y $ are special coins.
Each ordinary coin is initially *active*; special coins are always *inactive*.
Let $ \tau = (5, 2, 5, 2, 5, 2) $ be the merging thresholds for denominations $ A $ to $ F $, respectively.
A *four-connected component* is a maximal set of positions with coins of the same denomination, where any two positions are connected via four-adjacent steps ($ |x_1 - x_2| + |y_1 - y_2| = 1 $).
**Constraints**
1. $ 1 \leq n \leq 2000 $, $ 1 \leq m \leq 20 $
2. At most 20 special coins ($ X, Y $) exist initially.
3. Coin positions are indexed $ (i, j) $, $ i \in \{1, \dots, n\} $ (bottom to top), $ j \in \{1, \dots, m\} $ (left to right).
4. A position $ (x_1, y_1) $ is *over* $ (x_2, y_2) $ iff $ x_1 = x_2 + 1 $ and $ y_1 = y_2 $.
**Game Rules**
Each *round* proceeds as follows:
1. **Operation Selection**:
A valid operation is a pair $ (t, x) $, where $ t \in \{A, B, C, D, E, F, X, Y\} $, $ x \in \{1, \dots, m\} $, satisfying:
- If $ t \in \{A, B, C, D, E, F\} $: the four-connected component of type $ t $ in stack $ x $ contains at least one active coin and has size $ \geq \tau_{t} $,
- If $ t = X $: stack $ x $ contains at least one $ X $,
- If $ t = Y $: stack $ x $ contains at least one $ Y $,
- The operation yields score increment $ \geq 1 $.
2. **Execution**:
- **Case $ t \in \{X, Y\} $**:
- All coins of type $ t $ in stack $ x $ are removed; score increases by their count.
- If $ t = X $ and the denomination of $ y $ (the coin type being replaced) is $ < 500 $, then one *active* coin of the next higher denomination is placed at the *least* position among the removed positions.
- All coins of type $ y $ (the denomination of the coin replaced by $ X $) are *also* removed immediately; score increases by their count.
- If $ t = X $ and $ y < 500 $, then *active* coins of denomination $ y+1 $ are generated to replace *all* removed $ y $-coins.
*(Note: The description of step 2 is ambiguous and self-referential. We assume the intended semantics are: when $ (X, x) $ is chosen, all $ Y $ coins are removed and replaced by higher-denomination coins if applicable; when $ (Y, x) $ is chosen, all $ Y $ coins are removed.)*
- **Case $ t \in \{A, B, C, D, E, F\} $**:
- The largest four-connected component of type $ t $ in stack $ x $ (with size $ \geq \tau_t $ and at least one active coin) is removed.
- Score increases by the size of the component.
- If $ t < 500 $, one *active* coin of the next higher denomination is placed at the *least* position among the removed positions.
3. **Termination**:
The game ends when no valid operation exists.
**Objective**
Compute the sequence of rounds:
- Total number of rounds $ K $.
- For each round $ k \in \{1, \dots, K\} $: output $ (t_k, x_k, s_k) $, where:
- $ t_k \in \{A, B, C, D, E, F, X, Y\} $ is the chosen type,
- $ x_k \in \{1, \dots, m\} $ is the chosen stack,
- $ s_k \in \mathbb{Z}^+ $ is the score increment.
**Operation Priority**
Among all valid operations, the boy selects the *best* one by unknown criteria (not specified). Since priority is undefined, assume lexicographic order:
- Prefer smaller $ t $ in order $ A < B < C < D < E < F < X < Y $,
- Then prefer smaller $ x $.
*(Note: Problem states "best operation" but does not define comparison. This is a critical ambiguity. We assume lexicographic ordering for determinism.)*