В далёкой-далёкой Мексике растут целые плантации кактусов. А еще там живут начинающие жулики Карлос и Педро. Они посмотрели фильм «Крёстный отец» и решили стать крупными мафиози. Но контрабандисты, которые торгуют оружием и наркотиками, не взяли их к себе. Поэтому они решили продавать кактусы пылким иностранным коллекционерам. Придя на плантацию, Карлос и Педро обнаружили, что не унесут в руках огромный кактус. Тогда горе-бандиты решили разрезать его на кусочки, содержащие не больше двух ребер. Посчитайте возможное количество различных способов разрезать несчастный кактус. Возьмите это огромное, как горе Карлоса и Педро, число по модулю 10⁹ + 7.

Кактус — это связный неориентированный граф, в котором каждая вершина (в данной задаче она же колючка) лежит не более чем на одном простом цикле. Два способа считаются различными, если между одними и теми же колючками в одном разрезе есть ребро, а в другом его нет.