$NxN$ shahmat doskasi berilgan. Siz bu shahmat doskada $N$ ta ruxni joylashtirishingiz kerak-ki, ular bir-birini hujumi ostida bo'lmasin hamda hech qaysi rux dioganlda yotmasin. Barcha kombinatsiyalar sonini toping.

Kiruvchi ma’lumotlar

Birinchi qatorda 1 ta natural son, $n(1\le N\le 100)$.

Chiquvchi ma’lumotlar

Yagona qatorda masala yechimini chiqaring. Javob katta bo'lib ketishi mumkin, shuning uchun uni ${10}^9+7$ ga bo'lgandaki qoldiqini chiqaring.