문제
$N$개의 도시가 해안선을 따라 원형으로 배치되어 있다. 도시는 시계 방향으로 1ドル$번부터 $N$번까지 번호가 차례로 붙어 있다. 모든 도시 쌍에 대해, 해당 두 도시를 연결하는 양방향 직선 도로가 존재한다.
이 수많은 도로들 중, $a$번 도시와 $b$번 도시를 잇는 도로를 특별한 도로라고 부른다. 이 특별한 도로는 1ドル$번 도시가 아닌 두 도시를 이으며, 경치가 가장 아름다운 도로로 알려져 있다.
정서는 다음과 같은 방식으로, 도로만을 이용해 이 도시들을 여행하려 한다.
- 여행은 1ドル$번 도시에서 출발하며, 출발과 동시에 1ドル$번 도시는 이미 방문한 것으로 간주한다.
- 여행 중에는 1ドル$번 도시를 포함한 이미 방문한 도시를 다시 방문해서는 안 되며, 모든 도시를 정확히 한 번씩 방문해야 한다.
- 여행 중 이용하는 어떤 두 도로도 서로 교차하지 않아야 한다.
- 여행 중에는 반드시 특별한 도로를 한 번 이용해야 한다. 단, 특별한 도로를 이용하는 방향은 중요하지 않다.
위 조건을 모두 만족하는 이동 경로의 수를 구하시오.
출력
조건을 만족하는 모든 경로의 수를 1ドル,000円,000円,007円$로 나눈 나머지를 출력한다.
W3sicHJvYmxlbV9pZCI6IjM0MDU5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNTc0XHVjNTQ4XHVjMTIwIiwiZGVzY3JpcHRpb24iOiI8cD4kTiRcdWFjMWNcdWM3NTggXHViM2M0XHVjMmRjXHVhYzAwIFx1ZDU3NFx1YzU0OFx1YzEyMFx1Yzc0NCBcdWI1MzBcdWI3N2MgXHVjNmQwXHVkNjE1XHVjNzNjXHViODVjIFx1YmMzMFx1Y2U1OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YjNjNFx1YzJkY1x1YjI5NCBcdWMyZGNcdWFjYzQgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjICQxJFx1YmM4OFx1YmQ4MFx1ZDEzMCAkTiRcdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1Y2MyOFx1Yjg0MFx1Yjg1YyBcdWJkOTlcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHViM2M0XHVjMmRjIFx1YzMwZFx1YzVkMCBcdWIzMDBcdWQ1NzQsIFx1ZDU3NFx1YjJmOSBcdWI0NTAgXHViM2M0XHVjMmRjXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWM1OTFcdWJjMjlcdWQ1YTUgXHVjOWMxXHVjMTIwIFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWMyMThcdWI5Y2VcdWM3NDAgXHViM2M0XHViODVjXHViNGU0IFx1YzkxMSwgJGEkXHViYzg4IFx1YjNjNFx1YzJkY1x1YzY0MCAkYiRcdWJjODggXHViM2M0XHVjMmRjXHViOTdjIFx1Yzc4N1x1YjI5NCBcdWIzYzRcdWI4NWNcdWI5N2MgPHN0cm9uZz5cdWQyYjlcdWJjYzRcdWQ1NWMgXHViM2M0XHViODVjPFwvc3Ryb25nPlx1Yjc3Y1x1YWNlMCBcdWJkODBcdWI5NzhcdWIyZTQuIFx1Yzc3NCBcdWQyYjlcdWJjYzRcdWQ1NWMgXHViM2M0XHViODVjXHViMjk0ICQxJFx1YmM4OCBcdWIzYzRcdWMyZGNcdWFjMDAgXHVjNTQ0XHViMmNjIFx1YjQ1MCBcdWIzYzRcdWMyZGNcdWI5N2MgXHVjNzc0XHVjNzNjXHViYTcwLCBcdWFjYmRcdWNlNThcdWFjMDAgXHVhYzAwXHVjN2E1IFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZiNCBcdWIzYzRcdWI4NWNcdWI4NWMgXHVjNTRjXHViODI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVjMTFjXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViYzI5XHVjMmRkXHVjNzNjXHViODVjLCBcdWIzYzRcdWI4NWNcdWI5Y2NcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0IFx1Yzc3NCBcdWIzYzRcdWMyZGNcdWI0ZTRcdWM3NDQgXHVjNWVjXHVkNTg5XHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM1ZWNcdWQ1ODlcdWM3NDAgJDEkXHViYzg4IFx1YjNjNFx1YzJkY1x1YzVkMFx1YzExYyBcdWNkOWNcdWJjMWNcdWQ1NThcdWJhNzAsIFx1Y2Q5Y1x1YmMxY1x1YWNmYyBcdWIzZDlcdWMyZGNcdWM1ZDAgJDEkXHViYzg4IFx1YjNjNFx1YzJkY1x1YjI5NCBcdWM3NzRcdWJiZjggXHViYzI5XHViYjM4XHVkNTVjIFx1YWM4M1x1YzczY1x1Yjg1YyBcdWFjMDRcdWM4ZmNcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzVlY1x1ZDU4OSBcdWM5MTFcdWM1ZDBcdWIyOTQgJDEkXHViYzg4IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NWMgXHVjNzc0XHViYmY4IFx1YmMyOVx1YmIzOFx1ZDU1YyBcdWIzYzRcdWMyZGNcdWI5N2MgXHViMmU0XHVjMmRjIFx1YmMyOVx1YmIzOFx1ZDU3NFx1YzExY1x1YjI5NCBcdWM1NDggXHViNDE4XHViYTcwLCBcdWJhYThcdWI0ZTAgXHViM2M0XHVjMmRjXHViOTdjIFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YmMyOVx1YmIzOFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzVlY1x1ZDU4OSBcdWM5MTEgXHVjNzc0XHVjNmE5XHVkNTU4XHViMjk0IFx1YzViNFx1YjVhNCBcdWI0NTAgXHViM2M0XHViODVjXHViM2M0IFx1YzExY1x1Yjg1YyBcdWFkNTBcdWNjMjhcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNWVjXHVkNTg5IFx1YzkxMVx1YzVkMFx1YjI5NCBcdWJjMThcdWI0ZGNcdWMyZGMgPHN0cm9uZz5cdWQyYjlcdWJjYzRcdWQ1NWMgXHViM2M0XHViODVjPFwvc3Ryb25nPlx1Yjk3YyBcdWQ1NWMgXHViYzg4IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjJlOCwgXHVkMmI5XHViY2M0XHVkNTVjIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzQwIFx1YzkxMVx1YzY5NFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNzA0IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWJhYThcdWI0NTAgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1Yzc3NFx1YjNkOSBcdWFjYmRcdWI4NWNcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViM2M0XHVjMmRjXHVjNzU4IFx1YzIxOCAkTiRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoJDMgXFxsZXEgTiBcXGxlcSAxXFwsMDAwXFwsMDAwJCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQyYjlcdWJjYzRcdWQ1NWMgXHViM2M0XHViODVjXHVhYzAwIFx1Yzc4N1x1YjI5NCBcdWI0NTAgXHViM2M0XHVjMmRjXHVjNzU4IFx1YmM4OFx1ZDYzOCAkYSQsICRiJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKCQyXFxsZXEgYSwgYiBcXGxlcSBOJDsgJGFcXG5lcSBiJCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWFjYmRcdWI4NWNcdWM3NTggXHVjMjE4XHViOTdjICQxXFwsMDAwXFwsMDAwXFwsMDA3JFx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzNDA1OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvYXN0bGluZSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgYXJlICROJCBjaXRpZXMgb24gYSBjaXJjdWxhciBjb2FzdGxpbmUuIFRoZSBjaXRpZXMgYXJlIG51bWJlcmVkIGZyb20gJDEkIHRvICROJCBpbiBjbG9ja3dpc2Ugb3JkZXIuIEZvciBhbGwgcGFpcnMgb2YgY2l0aWVzLCB0aGVyZSBleGlzdHMgYSBiaWRpcmVjdGlvbmFsIHJvYWQgY29ubmVjdGluZyB0aGUgdHdvIGNpdGllcy48XC9wPlxyXG5cclxuPHA+QW1vbmcgYWxsIHRoZXNlIHJvYWRzLCB3ZSBjYWxsIHRoZSByb2FkIGNvbm5lY3RpbmcgdHdvIGNpdGllcyAkYSQgYW5kICRiJCB0aGUgPHN0cm9uZz5zcGVjaWFsIHJvYWQ8XC9zdHJvbmc+LiBUaGUgc3BlY2lhbCByb2FkIGNvbm5lY3RzIHR3byBjaXRpZXMsIG5laXRoZXIgb2Ygd2hpY2ggaXMgY2l0eSAkMSQsIGFuZCBpcyBrbm93biB0byBiZSB0aGUgcm9hZCB3aXRoIHRoZSBtb3N0IGJlYXV0aWZ1bCBzY2VuZXJ5LjxcL3A+XHJcblxyXG48cD5KZW9uZ3NlbyBwbGFucyB0byB0cmF2ZWwgdGhyb3VnaCB0aGUgY2l0aWVzIGZvbGxvd2luZyB0aGUgbWV0aG9kIGJlbG93LCBvbmx5IGJ5IHJvYWQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+SGlzIHRyYXZlbCBiZWdpbnMgYXQgY2l0eSAkMSQuIENpdHkgJDEkIGlzIGNvbnNpZGVyZWQgdG8gYmUgYWxyZWFkeSB2aXNpdGVkIGF0IHRoZSBtb21lbnQgaGUgYmVnaW5zIGhpcyB0cmF2ZWwuPFwvbGk+XHJcblx0PGxpPkR1cmluZyBoaXMgdHJhdmVsLCBoZSBzaG91bGQgbm90IHZpc2l0IGEgY2l0eSB0aGF0IGhlIGhhcyBhbHJlYWR5IHZpc2l0ZWQsIGluY2x1ZGluZyBjaXR5ICQxJCwgYW5kIGV2ZXJ5IGNpdHkgbXVzdCBiZSB2aXNpdGVkIGV4YWN0bHkgb25jZS48XC9saT5cclxuXHQ8bGk+Tm9uZSBvZiB0aGUgcm9hZHMgdXNlZCBpbiB0aGUgdHJhdmVsIGNvdXJzZSBtYXkgaW50ZXJzZWN0IHdpdGggZWFjaCBvdGhlci48XC9saT5cclxuXHQ8bGk+VGhlIDxzdHJvbmc+c3BlY2lhbCByb2FkPFwvc3Ryb25nPiBtdXN0IGJlIHVzZWQgZXhhY3RseSBvbmNlIGR1cmluZyBoaXMgdHJhdmVsLiBJdCBkb2VzIG5vdCBtYXR0ZXIgaW4gd2hpY2ggZGlyZWN0aW9uIGhlIHRyYXZlbHMgdGhyb3VnaCB0aGUgc3BlY2lhbCByb2FkLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkZpbmQgdGhlIG51bWJlciBvZiB0cmF2ZWwgcGF0aHMgdGhhdCBzYXRpc2Z5IGFsbCBvZiB0aGUgY29uZGl0aW9ucyBhYm92ZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgcG9zaXRpdmUgaW50ZWdlciAkTiQsIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgY2l0aWVzLiAoJDMgXFxsZXEgTiBcXGxlcSAxXFwsMDAwXFwsMDAwJCk8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgJGEkIGFuZCAkYiQsIGRlbm90aW5nIHRoZSB0d28gY2l0aWVzIGNvbm5lY3RlZCBieSB0aGUgc3BlY2lhbCByb2FkLiAoJDJcXGxlcSBhLCBiIFxcbGVxIE4kOyAkYVxcbmVxIGIkKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IHRoZSB0b3RhbCBudW1iZXIgb2YgcGF0aHMgdGhhdCBzYXRpc2Z5IHRoZSBjb25kaXRpb25zIGdpdmVuIGluIHRoZSBwcm9ibGVtIHN0YXRlbWVudCBtb2R1bG8gJDFcXCwwMDBcXCwwMDBcXCwwMDckLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=