문제
달구는 지난 2023년과 2024년에 열린 UDPC를 성공적으로 개최한 기념으로 윤이와 포닉스에게 보낼 자그마한 선물을 준비했다. 달구가 준비한 선물은 총 $N$개이고, 각 선물은 1ドル$번부터 $N$번까지의 번호가 붙어 있다.
달구는 준비한 모든 선물을 유니 또는 포닉스에게 보내려고 한다. 그러나 달구는 어떤 선물을 윤이에게 보낼지, 포닉스에게 보낼지를 아직 정하지 못했다. 달구는 $M$개의 조건을 세우고, 이 조건을 모두 만족하는 선에서 윤이와 포닉스에게 선물을 보내려고 한다. 달구가 세운 조건은 아래 세 가지 유형 중 하나이다.
- $a$ $b$
U: $a$번 선물과 $b$번 선물은 모두 윤이에게 보내야 한다.
- $a$ $b$
D: $a$번 선물과 $b$번 선물은 윤이와 포닉스에게 각각 하나씩 보내야 한다.
- $a$ $b$
P: $a$번 선물과 $b$번 선물은 모두 포닉스에게 보내야 한다.
달구가 윤이와 포닉스에게 선물을 보낼 수 있는 서로 다른 방법의 수를 10ドル^9 + 7$로 나눈 나머지를 구해보자. 어떤 두 방법이 서로 다르다는 것은 두 방법에서 윤이 또는 포닉스가 받을 선물 번호의 집합이 서로 다름을 의미한다. 만약 모든 조건을 만족하도록 각 선물을 윤이 또는 포닉스에게 보낼 수 없는 경우에는 대신 0을 출력한다.
출력
달구가 윤이와 포닉스에게 선물을 보낼 수 있는 서로 다른 방법의 수를 10ドル^9 + 7$로 나눈 나머지를 출력한다. 만약 모든 조건을 만족하도록 각 선물을 윤이 또는 포닉스에게 보낼 수 없는 경우에는 대신 0을 출력한다.
W3sicHJvYmxlbV9pZCI6IjMzNjk1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMTIwXHViYjNjIFx1YmNmNFx1YjBiNFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHViMmVjXHVhZDZjXHViMjk0IFx1YzljMFx1YjA5YyAyMDIzXHViMTQ0XHVhY2ZjIDIwMjRcdWIxNDRcdWM1ZDAgXHVjNWY0XHViOWIwIFVEUENcdWI5N2MgXHVjMTMxXHVhY2Y1XHVjODAxXHVjNzNjXHViODVjIFx1YWMxY1x1Y2Q1Y1x1ZDU1YyBcdWFlMzBcdWIxNTBcdWM3M2NcdWI4NWMgXHVjNzI0XHVjNzc0XHVjNjQwIFx1ZDNlY1x1YjJjOVx1YzJhNFx1YzVkMFx1YWM4YyBcdWJjZjRcdWIwYmMgXHVjNzkwXHVhZGY4XHViOWM4XHVkNTVjIFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWM5MDBcdWJlNDRcdWQ1ODhcdWIyZTQuIFx1YjJlY1x1YWQ2Y1x1YWMwMCBcdWM5MDBcdWJlNDRcdWQ1NWMgXHVjMTIwXHViYjNjXHVjNzQwIFx1Y2QxZCAkTiRcdWFjMWNcdWM3NzRcdWFjZTAsIFx1YWMwMSBcdWMxMjBcdWJiM2NcdWM3NDAgJDEkXHViYzg4XHViZDgwXHVkMTMwICROJFx1YmM4OFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNWI0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmVjXHVhZDZjXHViMjk0IFx1YzkwMFx1YmU0NFx1ZDU1YyBcdWJhYThcdWI0ZTAgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YzcyMFx1YjJjOCBcdWI2MTBcdWIyOTQgXHVkM2VjXHViMmM5XHVjMmE0XHVjNWQwXHVhYzhjIFx1YmNmNFx1YjBiNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YjA5OCBcdWIyZWNcdWFkNmNcdWIyOTQgXHVjNWI0XHViNWE0IFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWM3MjRcdWM3NzRcdWM1ZDBcdWFjOGMgXHViY2Y0XHViMGJjXHVjOWMwLCBcdWQzZWNcdWIyYzlcdWMyYTRcdWM1ZDBcdWFjOGMgXHViY2Y0XHViMGJjXHVjOWMwXHViOTdjIFx1YzU0NFx1YzljMSBcdWM4MTVcdWQ1NThcdWM5YzAgXHViYWJiXHVkNTg4XHViMmU0LiBcdWIyZWNcdWFkNmNcdWIyOTQgJE0kXHVhYzFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWMxMzhcdWM2YjBcdWFjZTAsIFx1Yzc3NCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViYWE4XHViNDUwIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWMxMjBcdWM1ZDBcdWMxMWMgXHVjNzI0XHVjNzc0XHVjNjQwIFx1ZDNlY1x1YjJjOVx1YzJhNFx1YzVkMFx1YWM4YyBcdWMxMjBcdWJiM2NcdWM3NDQgXHViY2Y0XHViMGI0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViMmVjXHVhZDZjXHVhYzAwIFx1YzEzOFx1YzZiNCBcdWM4NzBcdWFjNzRcdWM3NDAgXHVjNTQ0XHViNzk4IFx1YzEzOCBcdWFjMDBcdWM5YzAgXHVjNzIwXHVkNjE1IFx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JGEkICRiJCA8Y29kZT5VPFwvY29kZT46ICRhJFx1YmM4OCBcdWMxMjBcdWJiM2NcdWFjZmMgJGIkXHViYzg4IFx1YzEyMFx1YmIzY1x1Yzc0MCBcdWJhYThcdWI0NTAgPHN0cm9uZz5cdWM3MjRcdWM3NzQ8XC9zdHJvbmc+XHVjNWQwXHVhYzhjIFx1YmNmNFx1YjBiNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPiRhJCAkYiQgPGNvZGU+RDxcL2NvZGU+OiAkYSRcdWJjODggXHVjMTIwXHViYjNjXHVhY2ZjICRiJFx1YmM4OCBcdWMxMjBcdWJiM2NcdWM3NDAgXHVjNzI0XHVjNzc0XHVjNjQwIFx1ZDNlY1x1YjJjOVx1YzJhNFx1YzVkMFx1YWM4YyA8c3Ryb25nPlx1YWMwMVx1YWMwMSBcdWQ1NThcdWIwOThcdWM1Mjk8XC9zdHJvbmc+IFx1YmNmNFx1YjBiNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPiRhJCAkYiQgPGNvZGU+UDxcL2NvZGU+OiAkYSRcdWJjODggXHVjMTIwXHViYjNjXHVhY2ZjICRiJFx1YmM4OCBcdWMxMjBcdWJiM2NcdWM3NDAgXHViYWE4XHViNDUwIDxzdHJvbmc+XHVkM2VjXHViMmM5XHVjMmE0PFwvc3Ryb25nPlx1YzVkMFx1YWM4YyBcdWJjZjRcdWIwYjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YjJlY1x1YWQ2Y1x1YWMwMCBcdWM3MjRcdWM3NzRcdWM2NDAgXHVkM2VjXHViMmM5XHVjMmE0XHVjNWQwXHVhYzhjIFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWJjZjRcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgJDEwXjkgKyA3JFx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1Yzc5MC4gXHVjNWI0XHViNWE0IFx1YjQ1MCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDAgXHViNDUwIFx1YmMyOVx1YmM5NVx1YzVkMFx1YzExYyBcdWM3MjRcdWM3NzQgXHViNjEwXHViMjk0IFx1ZDNlY1x1YjJjOVx1YzJhNFx1YWMwMCBcdWJjMWJcdWM3NDQgXHVjMTIwXHViYjNjIFx1YmM4OFx1ZDYzOFx1Yzc1OCBcdWM5ZDFcdWQ1NjlcdWM3NzQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk4NFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWJhYThcdWI0ZTAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWFjMDEgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YzcyNFx1Yzc3NCBcdWI2MTBcdWIyOTQgXHVkM2VjXHViMmM5XHVjMmE0XHVjNWQwXHVhYzhjIFx1YmNmNFx1YjBiYyBcdWMyMTggXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWIzMDBcdWMyZTAgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPjA8XC9jb2RlPjxcL3NwYW4+XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmVjXHVhZDZjXHVhYzAwIFx1YzkwMFx1YmU0NFx1ZDU1YyBcdWMxMjBcdWJiM2NcdWM3NTggXHVjMjE4ICROJFx1YWNmYyBcdWMxMjBcdWJiM2NcdWM3NDQgXHViY2Y0XHViMGJjIFx1YjU0YyBcdWFjZTBcdWI4MjRcdWQ1NzRcdWM1N2MgXHVkNTYwIFx1Yzg3MFx1YWM3NFx1Yzc1OCBcdWMyMTggJE0kXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDIgXFxsZSBOIFxcbGUgMjAwXFwgMDAwOyAxIFxcbGUgTSBcXGxlIDIwMFxcIDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAkTSRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjQ1MCBcdWMxMjBcdWJiM2NcdWM3NTggXHViYzg4XHVkNjM4ICRhX2ksIGJfaSRcdWM2NDAgPGNvZGU+VTxcL2NvZGU+LCA8Y29kZT5EPFwvY29kZT4sIDxjb2RlPlA8XC9jb2RlPiBcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzU4IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxIFxcbGUgYV9pICZsdDsgYl9pIFxcbGUgTikkPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1YzVkMFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHViYWE4XHViNGUwIFx1YzIxOFx1YjI5NCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViMmVjXHVhZDZjXHVhYzAwIFx1YzcyNFx1Yzc3NFx1YzY0MCBcdWQzZWNcdWIyYzlcdWMyYTRcdWM1ZDBcdWFjOGMgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YmNmNFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyAkMTBeOSArIDckXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHViYWE4XHViNGUwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIzYzRcdWI4NWQgXHVhYzAxIFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWM3MjRcdWM3NzQgXHViNjEwXHViMjk0IFx1ZDNlY1x1YjJjOVx1YzJhNFx1YzVkMFx1YWM4YyBcdWJjZjRcdWIwYmMgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViMzAwXHVjMmUwIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4wPFwvY29kZT48XC9zcGFuPlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzM2OTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHaWZ0IERpc3RyaWJ1dGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+VG8gY2VsZWJyYXRlIHRoZSBzdWNjZXNzZnVsIGhvc3Rpbmcgb2YgVURQQyBpbiBib3RoIDIwMjMgYW5kIDIwMjQsIERhbGdvbyBwcmVwYXJlZCBzb21lIHNtYWxsIGdpZnRzIGZvciBZdW5lZSBhbmQgUG9uaXguIERhbGdvbyBoYXMgcHJlcGFyZWQgYSB0b3RhbCBvZiAkTiQgZ2lmdHMsIGVhY2ggbGFiZWxlZCB3aXRoIGEgbnVtYmVyIGZyb20gJDEkIHRvICROJC48XC9wPlxyXG5cclxuPHA+RGFsZ29vIHdhbnRzIHRvIHNlbmQgZWFjaCBnaWZ0Jm5ic3A7dG8gZWl0aGVyIFl1bmVlIG9yIFBvbml4LCBidXQgaGFzbiYjMzk7dCB5ZXQgZGVjaWRlZCB3aG8gd2lsbCByZWNlaXZlIGVhY2ggZ2lmdC4gVG8gaGVscCB3aXRoIHRoZSBkZWNpc2lvbiwgRGFsZ29vIGhhcyBlc3RhYmxpc2hlZCAkTSQgY29uZGl0aW9ucyBhbmQgd2FudHMgdG8gYXNzaWduIGVhY2ggZ2lmdCB0byBlaXRoZXIgWXVuZWUgb3IgUG9uaXggaW4gYSB3YXkgdGhhdCBzYXRpc2ZpZXMgYWxsIG9mIHRoZW0uIEVhY2ggY29uZGl0aW9uIGZhbGxzIGludG8gb25lIG9mIHRoZSBmb2xsb3dpbmcgdGhyZWUgdHlwZXM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JGEkICRiJCA8Y29kZT5VPFwvY29kZT46IEdpZnRzIG51bWJlcmVkICRhJCBhbmQgJGIkIG11c3QgYm90aCBiZSBzZW50IHRvIDxzdHJvbmcgZGF0YS1lbmQ9XCI2MDVcIiBkYXRhLXN0YXJ0PVwiNTk2XCI+WXVuZWU8XC9zdHJvbmc+LjxcL2xpPlxyXG5cdDxsaT4kYSQgJGIkIDxjb2RlPkQ8XC9jb2RlPjogR2lmdHMgbnVtYmVyZWQgJGEkIGFuZCAkYiQgbXVzdCBiZSBzZW50IHRvIFl1bmVlIGFuZCBQb25peCwgPHN0cm9uZz5vbmUgYnkgb25lPFwvc3Ryb25nPi48XC9saT5cclxuXHQ8bGk+JGEkICRiJCA8Y29kZT5QPFwvY29kZT46IEdpZnRzIG51bWJlcmVkICRhJCBhbmQgJGIkIG11c3QgYm90aCBiZSBzZW50IHRvIDxzdHJvbmcgZGF0YS1lbmQ9XCI3NTZcIiBkYXRhLXN0YXJ0PVwiNzQ3XCI+UG9uaXg8XC9zdHJvbmc+LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkRldGVybWluZSB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCB3YXlzIERhbGdvbyBjYW4gc2VuZCBnaWZ0cyB0byBZdW5lZSBhbmQgUG9uaXgsIG1vZHVsbyAkMTBeOSArIDckLiBUd28gd2F5cyBhcmUgY29uc2lkZXJlZCBkaWZmZXJlbnQgaWYgdGhlIHNldHMgb2YgZ2lmdHMgcmVjZWl2ZWQgYnkgWXVuZWUgb3IgUG9uaXggYXJlIGRpZmZlcmVudC4mbmJzcDtJZiB0aGVyZSBpcyBubyB3YXkgdG8gc2VuZCBlYWNoIGdpZnQgdG8gZWl0aGVyIFl1bmVlIG9yIFBvbml4IHdoaWxlIHNhdGlzZnlpbmcgYWxsIGNvbmRpdGlvbnMsIHByaW50IDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4wPFwvY29kZT48XC9zcGFuPiZuYnNwO2luc3RlYWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyAkTiQsIHRoZSBudW1iZXIgb2YgZ2lmdHMgcHJlcGFyZWQgYnkgRGFsZ29vLCBhbmQgJE0kLCB0aGUgbnVtYmVyIG9mIGNvbmRpdGlvbnMgdG8gYmUgY29uc2lkZXJlZCB3aGVuIHNlbmRpbmcgdGhlIGdpZnRzLCBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gJCgyIFxcbGUgTiBcXGxlIDIwMFxcIDAwMDsgMSBcXGxlIE0gXFxsZSAyMDBcXCAwMDApJDxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcmbmJzcDskTSQmbmJzcDtsaW5lcyBvZiBpbnB1dCBjb250YWluIHRoZSBudW1iZXJzICRhX2ksIGJfaSQgJm5ic3A7YW5kIG9uZSBvZiB0aGUgbGV0dGVycyA8Y29kZT5VPFwvY29kZT4sIDxjb2RlPkQ8XC9jb2RlPiwgPGNvZGU+UDxcL2NvZGU+LCBzZXBhcmF0ZWQgYnkgc3BhY2VzLiAkKDEgXFxsZSBhX2kmbmJzcDsmbHQ7IGJfaSBcXGxlIE4pJDxcL3A+XHJcblxyXG48cD5BbGwgbnVtYmVycyBnaXZlbiBpbiB0aGUgaW5wdXQgYXJlIGludGVnZXJzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHdheXMgRGFsZ29vIGNhbiBzZW5kIGdpZnRzIHRvIFl1bmVlIGFuZCBQb25peCwgbW9kdWxvICQxMF45ICsgNyQuJm5ic3A7SWYgdGhlcmUgaXMgbm8gd2F5IHRvIHNlbmQgZWFjaCBnaWZ0IHRvIGVpdGhlciBZdW5lZSBvciBQb25peCB3aGlsZSBzYXRpc2Z5aW5nIGFsbCBjb25kaXRpb25zLCBwcmludCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+MDxcL2NvZGU+PFwvc3Bhbj4mbmJzcDtpbnN0ZWFkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=