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

Вхідні дані

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

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

Вихідні дані

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

Обмеження

• ~1≤k≤n≤10^6~

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

6 
(()

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

2

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