У Фомы Дора скоро день рождения, и его друг Габи решил подготовить ему подарок. Он знает, что Фома Дор без ума от правильных последовательностей из круглых скобок длины ровно n.

Последовательность круглых скобок называется правильной, если выполнены следующие условия:

1. количество открывающих скобок в последовательности равно количеству закрывающих скобок
2. для любого префикса последовательности количество открывающих скобок на этом префиксе не меньше количества закрывающих скобок на этом префиксе.

Габи купил строчку s длины m (m ≤ n) и хочет дополнить её до правильной скобочной последовательности длины n. Для этого он выберет какие-то последовательности скобок p и q и получит строку p + s + q, то есть припишет p в начало строки s и q в конец строки s.

Теперь ему интересно, сколько существует пар строк p и q, таких что строка p + s + q является правильной скобочной последовательностью длины n. Вычислите это значение по модулю 10⁹ + 7.