문제
흐즈로는 그래프 이론을 공부하다가 흥미로운 그래프를 발견했습니다. 다음의 특징을 가지는 단순 무향 그래프를 Y라고 부릅시다.
- 4ドル$개의 정점과 3ドル$개의 간선을 가집니다.
- 하나의 정점을 루트라고 부르며, 나머지 3ドル$개의 정점을 리프라고 부릅니다.
- 3ドル$개의 간선은 각각의 리프와 루트를 연결합니다.
흐즈로는 Y의 성질이 매우 특이하다고 생각하여, 어떤 그래프 안에 Y가 몇 개나 존재하는지 세어 보기로 했습니다. 단순 무향 그래프에서 Y의 개수를 다음과 같이 정의합시다.
- 그래프에서 3ドル$개의 간선을 순서 없이 골랐을 때, 그 간선과 간선이 연결하는 정점들이 이루는 그래프가 Y가 되는 경우의 수를 그래프의 Y의 개수로 정의합니다.
단순 무향 그래프가 입력으로 주어질 때, 주어진 그래프의 Y의 개수를 출력하세요. 단, 개수가 너무 많을 수 있으니 개수를 소수 10ドル^9+7$로 나눈 나머지를 출력하세요.
출력
주어진 그래프의 Y의 개수를 10ドル^9 + 7$로 나눈 나머지를 출력하세요.
그래프에서 간선 3ドル$개를 선택해 만들어진 부분 그래프가 Y가 되는 경우는 다음과 같습니다.
- $(1,2),ドル $(1,3),ドル $(1,4)$를 선택합니다.
- $(1,2),ドル $(2,3),ドル $(2,4)$를 선택합니다.
- $(1,3),ドル $(2,3),ドル $(3,4)$를 선택합니다.
- $(1,4),ドル $(2,4),ドル $(3,4)$를 선택합니다.
따라서 예제의 그래프의 Y의 개수는 4ドル$입니다. 4ドル \equiv 4 \pmod{10^9+7}$이므로 4ドル$를 출력해야 합니다.
W3sicHJvYmxlbV9pZCI6IjMxMjE3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiWSIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNzUwXHVjOTg4XHViODVjXHViMjk0IFx1YWRmOFx1Yjc5OFx1ZDUwNCBcdWM3NzRcdWI4NjBcdWM3NDQgXHVhY2Y1XHViZDgwXHVkNTU4XHViMmU0XHVhYzAwIFx1ZDc2NVx1YmJmOFx1Yjg1Y1x1YzZiNCBcdWFkZjhcdWI3OThcdWQ1MDRcdWI5N2MgXHViYzFjXHVhY2FjXHVkNTg4XHVjMmI1XHViMmM4XHViMmU0LiBcdWIyZTRcdWM3NGNcdWM3NTggXHVkMmI5XHVjOWQ1XHVjNzQ0IFx1YWMwMFx1YzljMFx1YjI5NCBcdWIyZThcdWMyMWMgXHViYjM0XHVkNWE1IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yjk3YyA8c3Ryb25nPlk8XC9zdHJvbmc+XHViNzdjXHVhY2UwIFx1YmQ4MFx1Yjk4NVx1YzJkY1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kNCRcdWFjMWNcdWM3NTggXHVjODE1XHVjODEwXHVhY2ZjICQzJFx1YWMxY1x1Yzc1OCBcdWFjMDRcdWMxMjBcdWM3NDQgXHVhYzAwXHVjOWQxXHViMmM4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWQ1NThcdWIwOThcdWM3NTggXHVjODE1XHVjODEwXHVjNzQ0IDxzdHJvbmc+XHViOGU4XHVkMmI4PFwvc3Ryb25nPlx1Yjc3Y1x1YWNlMCBcdWJkODBcdWI5NzRcdWJhNzAsIFx1YjA5OFx1YmEzOFx1YzljMCAkMyRcdWFjMWNcdWM3NTggXHVjODE1XHVjODEwXHVjNzQ0IDxzdHJvbmc+XHViOWFjXHVkNTA0PFwvc3Ryb25nPlx1Yjc3Y1x1YWNlMCBcdWJkODBcdWI5ODVcdWIyYzhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPiQzJFx1YWMxY1x1Yzc1OCBcdWFjMDRcdWMxMjBcdWM3NDAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YjlhY1x1ZDUwNFx1YzY0MCBcdWI4ZThcdWQyYjhcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTY5XHViMmM4XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1ZDc1MFx1Yzk4OFx1Yjg1Y1x1YjI5NCA8c3Ryb25nPlk8XC9zdHJvbmc+XHVjNzU4IFx1YzEzMVx1YzljOFx1Yzc3NCBcdWI5ZTRcdWM2YjAgXHVkMmI5XHVjNzc0XHVkNTU4XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YzVlYywgXHVjNWI0XHViNWE0IFx1YWRmOFx1Yjc5OFx1ZDUwNCBcdWM1NDhcdWM1ZDAgPHN0cm9uZz5ZPFwvc3Ryb25nPlx1YWMwMCBcdWJhODcgXHVhYzFjXHViMDk4IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NFx1YzljMCBcdWMxMzhcdWM1YjQgXHViY2Y0XHVhZTMwXHViODVjIFx1ZDU4OFx1YzJiNVx1YjJjOFx1YjJlNC4gXHViMmU4XHVjMjFjIFx1YmIzNFx1ZDVhNSBcdWFkZjhcdWI3OThcdWQ1MDRcdWM1ZDBcdWMxMWMgPHN0cm9uZz5ZXHVjNzU4IFx1YWMxY1x1YzIxODxcL3N0cm9uZz5cdWI5N2MgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM4MTVcdWM3NThcdWQ1NjlcdWMyZGNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVhZGY4XHViNzk4XHVkNTA0XHVjNWQwXHVjMTFjICQzJFx1YWMxY1x1Yzc1OCBcdWFjMDRcdWMxMjBcdWM3NDQgXHVjMjFjXHVjMTFjIFx1YzVjNlx1Yzc3NCBcdWFjZThcdWI3OTBcdWM3NDQgXHViNTRjLCBcdWFkZjggXHVhYzA0XHVjMTIwXHVhY2ZjIFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjODE1XHVjODEwXHViNGU0XHVjNzc0IFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWFkZjhcdWI3OThcdWQ1MDRcdWFjMDAgPHN0cm9uZz5ZPFwvc3Ryb25nPlx1YWMwMCBcdWI0MThcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggPHN0cm9uZz5ZXHVjNzU4IFx1YWMxY1x1YzIxODxcL3N0cm9uZz5cdWI4NWMgXHVjODE1XHVjNzU4XHVkNTY5XHViMmM4XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YjJlOFx1YzIxYyBcdWJiMzRcdWQ1YTUgXHVhZGY4XHViNzk4XHVkNTA0XHVhYzAwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IDxzdHJvbmc+WVx1Yzc1OCBcdWFjMWNcdWMyMTg8XC9zdHJvbmc+XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzEzOFx1YzY5NC4gXHViMmU4LCBcdWFjMWNcdWMyMThcdWFjMDAgXHViMTA4XHViYjM0IFx1YjljZVx1Yzc0NCBcdWMyMTggXHVjNzg4XHVjNzNjXHViMmM4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWMxOGNcdWMyMTggJDEwXjkrNyRcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMxMzhcdWM2OTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4ICRuJFx1YWNmYyBcdWFjMDRcdWMxMjBcdWM3NTggXHVhYzFjXHVjMjE4ICRtJFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHViZDg0XHViOWFjXHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gKCQxIFxcbGUgbiBcXGxlIDEwXjUkLCAkMCBcXGxlIG0gXFxsZSBcXG1pbihcXGZyYWN7bihuLTEpfXsyfSwyXFx0aW1lcyAxMF41KSQpPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwICRtJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgJGkkXHViYzg4XHVjOWY4IFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjODE1XHVjODEwICR1JFx1YzY0MCAkdiRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YmQ4NFx1YjlhY1x1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuICgkMSBcXGxlIHUsdiBcXGxlIG4kLCAkdSBcXG5lcSB2JCk8XC9wPlxyXG5cclxuPHA+XHVjOGZjXHVjNWI0XHVjOWM0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YjI5NCBcdWM5MTFcdWJjZjUgXHVhYzA0XHVjMTIwXHVjNzc0XHViMDk4IFx1YzU5MSBcdWIwNWRcdWM4MTBcdWM3NzQgXHVhYzE5XHVjNzQwIFx1YWMwNFx1YzEyMFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWM5YzAgXHVjNTRhXHVjNzRjXHVjNzc0IFx1YmNmNFx1YzdhNVx1YjQyOVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4ZmNcdWM1YjRcdWM5YzQgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IDxzdHJvbmc+WVx1Yzc1OCBcdWFjMWNcdWMyMTg8XC9zdHJvbmc+XHViOTdjICQxMF45ICsgNyRcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMxMzhcdWM2OTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPlx1YWRmOFx1Yjc5OFx1ZDUwNFx1YzVkMFx1YzExYyBcdWFjMDRcdWMxMjAgJDMkXHVhYzFjXHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU3NCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM5YzQgXHViZDgwXHViZDg0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YWMwMCZuYnNwOzxzdHJvbmc+WTxcL3N0cm9uZz5cdWFjMDAgXHViNDE4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjMmI1XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiQoMSwyKSQsICQoMSwzKSQsICQoMSw0KSRcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTY5XHViMmM4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT4kKDEsMikkLCAkKDIsMykkLCAkKDIsNCkkXHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU2OVx1YjJjOFx1YjJlNC48XC9saT5cclxuXHQ8bGk+JCgxLDMpJCwgJCgyLDMpJCwgJCgzLDQpJFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPiQoMSw0KSQsICQoMiw0KSQsICQoMyw0KSRcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTY5XHViMmM4XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YjUzMFx1Yjc3Y1x1YzExYyBcdWM2MDhcdWM4MWNcdWM3NTggXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IDxzdHJvbmc+WVx1Yzc1OCBcdWFjMWNcdWMyMTg8XC9zdHJvbmc+XHViMjk0ICQ0JFx1Yzc4NVx1YjJjOFx1YjJlNC4gJDQgXFxlcXVpdiA0IFxccG1vZHsxMF45Kzd9JFx1Yzc3NFx1YmJjMFx1Yjg1YyAkNCRcdWI5N2MgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU2OVx1YjJjOFx1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIzMTIxNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlkiLCJkZXNjcmlwdGlvbiI6IjxwPldoaWxlIHN0dWR5aW5nIGdyYXBoIHRoZW9yeSwgQ2hyb21hdGUgZm91bmQgYW4gaW50ZXJlc3RpbmcgdHlwZSBvZiBncmFwaHMuIExldCB1cyBjYWxsIGEgc2ltcGxlIHVuZGlyZWN0ZWQgZ3JhcGggPHN0cm9uZz5ZPFwvc3Ryb25nPiBpZiBpdCBoYXMgdGhlIGZvbGxvd2luZyBwcm9wZXJ0aWVzLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkl0IGNvbnRhaW5zICQ0JCB2ZXJ0aWNlcyBhbmQgJDMkIGVkZ2VzLjxcL2xpPlxyXG5cdDxsaT5PbmUgdmVydGV4IGlzIGNhbGxlZCB0aGUgPHN0cm9uZz5yb290PFwvc3Ryb25nPiwgYW5kIHRoZSAkMyQgb3RoZXIgdmVydGljZXMgYXJlIGNhbGxlZCB0aGUgPHN0cm9uZz5sZWF2ZXM8XC9zdHJvbmc+LjxcL2xpPlxyXG5cdDxsaT5FYWNoIG9mIHRoZSAkMyQgZWRnZXMgY29ubmVjdCB0aGUgcm9vdCBhbmQgb25lIGxlYWYuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Q2hyb21hdGUsIHRoaW5raW5nIHRoYXQgdGhlIHByb3BlcnR5IG9mIDxzdHJvbmc+WTxcL3N0cm9uZz4gaXMgdmVyeSB1bmlxdWUsIGRlY2lkZWQgdG8gY291bnQgaG93IG1hbnkgPHN0cm9uZz5ZPFwvc3Ryb25nPiZuYnNwO2FyZSBjb250YWluZWQgaW4gc29tZSBncmFwaC4gTGV0IHVzIGRlZmluZSB0aGUgPHN0cm9uZz5jYXJkaW5hbGl0eSBvZiBZPFwvc3Ryb25nPiBvZiBhIHNpbXBsZSB1bmRpcmVjdGVkIGdyYXBoIGFzIGZvbGxvd3MuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+V2hlbiB3ZSBzZWxlY3QgJDMkIGRpZmZlcmVudCBlZGdlcyB3aXRob3V0IG9yZGVyIGluIHRoZSBncmFwaCwgdGhlIG51bWJlciBvZiBjYXNlcyBzdWNoIHRoYXQgdGhlIGdyYXBoIGNvbnNpc3Rpbmcgb2YgdGhlIGVkZ2VzIGFuZCBhbGwgaW5jaWRlbnQgdmVydGljZXMgaXMgPHN0cm9uZz5ZPFwvc3Ryb25nPiwgaXMgY2FsbGVkIHRoZSA8c3Ryb25nPmNhcmRpbmFsaXR5IG9mIFk8XC9zdHJvbmc+Jm5ic3A7b2YgdGhhdCBncmFwaC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5HaXZlbiBhIHNpbXBsZSB1bmRpcmVjdGVkIGdyYXBoIGFzIGlucHV0LCBvdXRwdXQgdGhlIDxzdHJvbmc+Y2FyZGluYWxpdHkgb2YgWTxcL3N0cm9uZz4mbmJzcDtvZiB0aGUgZ2l2ZW4gZ3JhcGguIEFzIHRoZSBhbnN3ZXIgY2FuIGJlIHRvbyBsYXJnZSwgeW91IHNob3VsZCBvdXRwdXQgdGhlIGFuc3dlciBtb2R1bG8gJDEwXjkrNyQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSwgdHdvIGludGVnZXJzICRuJCBhbmQgJG0kICZtZGFzaDsgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBhbmQgZWRnZXMgJm1kYXNoOyBhcmUgZ2l2ZW4uICgkMSBcXGxlIG4gXFxsZSAxMF41JCwgJDAgXFxsZSBtIFxcbGUgXFxtaW4oXFxmcmFje24obi0xKX17Mn0sMlxcdGltZXMgMTBeNSkkKTxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgJG0kIGxpbmVzIGNvbnRhaW4gdHdvIHZlcnRpY2VzICR1JCBhbmQgJHYkIGNvbm5lY3RlZCBieSB0aGUgJGkkLXRoIGVkZ2UuICgkMSBcXGxlIHUsdiBcXGxlIG4kLCAkdSBcXG5lcSB2JCk8XC9wPlxyXG5cclxuPHA+SXQgaXMgZ3VhcmFudGVlZCB0aGF0IHRoZSBnaXZlbiBncmFwaCBkb2VzIG5vdCBjb250YWluIGR1cGxpY2F0ZSBlZGdlcyBvciBzZWxmIGxvb3BzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk9uIG9uZSBsaW5lLCBvdXRwdXQgdGhlIDxzdHJvbmc+Y2FyZGluYWxpdHkgb2YgWTxcL3N0cm9uZz4gb2YgdGhlIGdpdmVuIGdyYXBoIG1vZHVsbyAkMTBeOSs3JC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPlRoZSBjYXNlcyB0aGF0IHRoZSBzdWJncmFwaCBjb25zdHJ1Y3RlZCBieSBzZWxlY3RpbmcgJDMkIGVkZ2VzIGlzIDxzdHJvbmc+WTxcL3N0cm9uZz4mbmJzcDtpcyBhcyBmb2xsb3dzLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlNlbGVjdCZuYnNwOyQoMSwyKSQsICQoMSwzKSQsICQoMSw0KSQuPFwvbGk+XHJcblx0PGxpPlNlbGVjdCAkKDEsMikkLCAkKDIsMykkLCAkKDIsNCkkLjxcL2xpPlxyXG5cdDxsaT5TZWxlY3QgJCgxLDMpJCwgJCgyLDMpJCwgJCgzLDQpJC48XC9saT5cclxuXHQ8bGk+U2VsZWN0ICQoMSw0KSQsICQoMiw0KSQsICQoMyw0KSQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlcmVmb3JlLCB0aGUgPHN0cm9uZz5jYXJkaW5hbGl0eSBvZiBZPFwvc3Ryb25nPiBvZiB0aGUgZ3JhcGggZ2l2ZW4gaW4gdGhlIGV4YW1wbGVzIGlzICQ0JC4gQXMgJDQgXFxlcXVpdiA0IFxccG1vZHsxMF45Kzd9JCwgeW91IHNob3VsZCBvdXRwdXQgJDQkLjxcL3A+XHJcbiJ9XQ==