Ваше завдання полягає в тому, щоб обчислити кількість правильних послідовностей дужок довжини \(n\), якщо задано префікс послідовності.

Вхідні дані

У першому рядку є ціле число \(n\).

Другий рядок містить \(k\) символів: префікс послідовності.

Вихідні дані

Вивести кількість послідовностей за модулем \(10^9+7\).

Обмеження

• \(1≤k≤n≤10^6\)

Приклад вхідних даних

6 
(()

Приклад вихідних даних

2

Пояснення: Є є дві можливі послідовності: (())() і (()()).