Неко играл в свои игрушки на заднем дворе дома Аки. Аки решил его разыграть и подбросил в его игрушки немного кошачей мяты. К сожалению он немного переборщил и случайно подбросил целый пакет мяты...
Неко понадобилось больше дня чтобы вернутся в нормальное состояние, после чего он рассказал, что увидел за это время много странных вещей, например он видел бор всех правильных скобочных последовательностей длины \(2n\).
Правильные скобочные последовательности определяются следующим образом:
- Пустая последовательность является правильной скобочной последовательностью.
- Если \(s\) является правильной скобочной последовательностью, то \((\,s\,)\) тоже является правильной скобочной последовательностью,
- Если \(s\) и \(t\) образуют правильную скобочную последовательность, то \(st\) тоже является правильной скобочной последовательностью.
Например, строки «(())» и «()()» образуют правильную скобочную последовательность, а строки «)(» и «((» нет.
Аки затем придумал интересную задачку. Он хочет узнать чему равен размер максимального паросочетания (то есть множества рёбер с непересекающимися концами) в этом дереве? Так как ответ может быть достаточно большим, выведите его по модулю \(10^9 + 7\).
Выходные данные
Выведите одно число — размер наибольшего паросочетания в дереве. Так как ответ может быть достаточно большим, выведите его по модулю \(10^9 + 7\).
Примечание
Картинки ниже иллюстрируют бор в первом и втором примере (для наглядности круглые скобки заменены на угловые). Максимальное паросочетание обозначено синим.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
|
1
|
|
2
|
2
|
3
|
|
3
|
3
|
9
|