H. Nate and High School Nakama
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 nakamas, 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?

Input

The input consists of a line with a single integer $$$n$$$, the number of students in the class.

Constraints

$$$1 \leq n \leq 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.

Examples
Input
3
Output
13
Input
41
Output
680415236
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.