Во Министерството за транспорт работат N лица. Како и секаде, сите различно се вложуваат во работата.

Со цел побрза реализација на нов проект за изградба на автопати, потребно е да се променат N закони, па вработените во министерството треба да подготват по еден предлог амандман за секој од законите. Министерот треба да ја распредели работата на подготовка на овие N амандмани на N-те лица вработени во министерството.

Денес, тој ги повикал сите вработени и ги замолил да се наредат во една редица според тоа колку амандмани сакаат да добијат за подготовка. Интересно, од кога се наредиле вработените, излегло дека првиот вработен сака да добие N амандмани (сите), вториот во редицата сака точно (N-1) амандмани, третиот (N-2) амандмани итн, до последниот кој сака да добие само 1 амандман.

Министерот сега се прашува колку различни распределувања на работата постојат, така што барем еден од вработените ќе биде задоволен од распределувањето (т.е. ќе добие точно толку амандмани за подготовка колку што побарал)? Две распределувања (прво и второ) се разликуваат меѓусебно, доколку постои амандман за одреден закон кој во првото распределување се дава на еден вработен (на пример, на 5-тиот вработен), а во второто распределување не му се дава нему туку на некој друг.

Влез

Во првиот ред е запишан еден цел број N (1 <= N <= 300), кој го означува бројот на вработени (исто и бројот на закони).

Забелешка:
Во тест случаи кои носат најмалку 17% од поените, ќе важи N <= 6.
Во други тест случаи кои носат најмалку 12% од поените, ќе важи N <= 10.
Во други тест случаи кои носат најмалку 18% од поените, ќе важи N <= 18.

Излез

Отпечатете го бараниот број на распределувања на работата каде што барем еден вработен ќе биде задоволен, по модул 1000000007 (бидејќи резултатот може да е многу голем број). За дадени два цели броја А и B, A модул B го означува остатокот кој се добива при делење на A со B. На пример, бројот 7 станува 1 по модул 3.

Ограничувања

Временско ограничување: 100 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
2

излез
3

Постојат два вработени. Првиот сака да добие N=2 закони, а вториот 1 закон.

Одговорот е 3, бидејќи постојат 3 распределувања на работата каде што барем еден вработен е задоволен:
1. Првиот вработен да е задолжен за првиот закон, а вториот за вториот закон (задоволен е вториот вработен, бидејќи добива точно 1 закон).
2. Првиот вработен да е задолжен за вториот закон, а вториот за првиот закон (повторно, задоволен е вториот вработен, бидејќи добива точно 1 закон).
3. Првиот вработен да добие два закони, а вториот да не добие ништо (задоволен е првиот вработен, бидејќи добива точно 2 закони).