Ada the Ladybug is a great farmer. She has many places where she grows vegetables. She wants to grow two completely different kinds of vegetable: carrots and baby carrots. She wants to connect them by paths in such way, that she can get from any carrot (or baby carrot) to any other carrot (or baby carrot). She isn't amused by building itself, so she wants to make least number of paths, which is sufficient to make all carrots (and all baby carrots) connected. Due to regulations of Earwigean Union (EU), a carrot can't be connected to other carrot (and same is true for baby carrots) [so basically, she can connect only "baby carrots" to "carrots"]. Ada also wants to keep track of everything, so she will somehow distinguish between each carrot and between each baby carrot (and also between each place).

She is wondering in how many ways she can plant carrots (and baby carrots) and connect them by ways, so that it corresponds to EU regulations.

Input

The input contains up to 200 lines. Each line consists of single integer 2 ≤ N ≤ 2*10⁵ , the number of places to which carrots/baby carrots shall be placed (note that she won't waste so she will fill all the places).

Output

For each line of input, print the number of ways, to plant carrots and baby carrots in such way, that it coresponds to EU regulations. Since this number might be pretty big, output it modulo 10⁹+7 (1000000007)

Example Input

2
3
4
10
66666

Example Output

2
12
144
452744977
57191401