Sizga $n$ soni berilgan. Siz $n$ ta ochiluvchi va yopiluvchi qavslar orqali to'g'ri qavsli ketma-ketliklardan qanchani yasasa bo'lishini toping.

Kiruvchi ma’lumotlar

Birinchi qatorda 1 ta natural son, $n(1 \le n \le 10^5)$.

Chiquvchi ma’lumotlar

Yagona qatorda masala yechimini chiqaring. Javob katta bo'lib ketishi mumkin. Shuning uchun javobni $10^9 + 7$ ga bo'lgandaki qoldiqini chiqaring.

Izoh:

$n = 1$ holat uchun: $()$.

$n = 2$ holat uchun: $(()), ()()$.

$n = 3$ holat uchun: $((())), ()(()), ()()(), (()()), (())()$.