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