문제
U, D, P로만 이루어져 있으며 U, D, P가 모두 동일한 개수가 들어 있는 문자열을 UDP 문자열이라고 한다. 또한, 어떤 두 개의 UDP 문자열을 이어 붙여도 만들 수 없는 UDP 문자열을 완전 UDP 문자열이라고 한다. 가령, 문자열 UDPPUD는 두 UDP 문자열 UDP와 PUD를 이어붙여 만들 수 있으므로 완전 UDP 문자열이 아니지만, UUDDPP는 완전 UDP 문자열이다.
길이 3ドルN$인 완전 UDP 문자열의 개수를 구해보자. 단, 답이 매우 클 수 있으므로 답을 10ドル^9+7$로 나눈 나머지를 구해보자.
출력
길이 3ドルN$인 완전 UDP 문자열의 개수를 10ドル^9+7$로 나눈 나머지를 출력한다.
길이 3ドル$의 완전 UDP 문자열은 UDP, UPD, DUP, DPU, PUD, PDU로 총 6ドル$개다.
W3sicHJvYmxlbV9pZCI6IjMzNjk2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiVURQIFx1YmIzOFx1Yzc5MFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPlU8XC9jb2RlPjxcL3NwYW4+LCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+RDxcL2NvZGU+PFwvc3Bhbj4sIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5QPFwvY29kZT48XC9zcGFuPlx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5VPFwvY29kZT48XC9zcGFuPiwgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPkQ8XC9jb2RlPjxcL3NwYW4+LCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+UDxcL2NvZGU+PFwvc3Bhbj5cdWFjMDAgXHViYWE4XHViNDUwIFx1YjNkOVx1Yzc3Y1x1ZDU1YyBcdWFjMWNcdWMyMThcdWFjMDAgXHViNGU0XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgPHN0cm9uZz5VRFAgXHViYjM4XHVjNzkwXHVjNWY0PFwvc3Ryb25nPlx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjYxMFx1ZDU1YywgXHVjNWI0XHViNWE0IFx1YjQ1MCBcdWFjMWNcdWM3NTggVURQIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWM3NzRcdWM1YjQgXHViZDk5XHVjNWVjXHViM2M0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNWM2XHViMjk0IFVEUCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgPHN0cm9uZz5cdWM2NDRcdWM4MDQgVURQIFx1YmIzOFx1Yzc5MFx1YzVmNDxcL3N0cm9uZz5cdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFjMDBcdWI4MzksIFx1YmIzOFx1Yzc5MFx1YzVmNCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+VURQUFVEPFwvY29kZT48XC9zcGFuPlx1YjI5NCBcdWI0NTAgVURQIFx1YmIzOFx1Yzc5MFx1YzVmNCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+VURQPFwvY29kZT48XC9zcGFuPlx1YzY0MCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+UFVEPFwvY29kZT48XC9zcGFuPlx1Yjk3YyBcdWM3NzRcdWM1YjRcdWJkOTlcdWM1ZWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMgXHVjNjQ0XHVjODA0IFVEUCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjNTQ0XHViMmM4XHVjOWMwXHViOWNjLCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+VVVERFBQPFwvY29kZT48XC9zcGFuPlx1YjI5NCBcdWM2NDRcdWM4MDQgVURQIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZTM4XHVjNzc0ICQzTiRcdWM3NzggXHVjNjQ0XHVjODA0IFVEUCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1Yzc5MC4gXHViMmU4LCBcdWIyZjVcdWM3NzQgXHViOWU0XHVjNmIwIFx1ZDA3NCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYmMwXHViODVjIFx1YjJmNVx1Yzc0NCAkMTBeOSs3JFx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFVEUCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjICQzJFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHVjODE1XHVjMjE4ICROJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMVxcbGVxIE5cXGxlcSA1XFwsMDAwKSQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFlMzhcdWM3NzQgJDNOJFx1Yzc3OCBcdWM2NDRcdWM4MDQgVURQIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgJDEwXjkrNyRcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPlx1YWUzOFx1Yzc3NCAkMyRcdWM3NTggXHVjNjQ0XHVjODA0IFVEUCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPlVEUDxcL2NvZGU+PFwvc3Bhbj4sIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5VUEQ8XC9jb2RlPjxcL3NwYW4+LCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+RFVQPFwvY29kZT48XC9zcGFuPiwgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPkRQVTxcL2NvZGU+PFwvc3Bhbj4sIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5QVUQ8XC9jb2RlPjxcL3NwYW4+LCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+UERVPFwvY29kZT48XC9zcGFuPlx1Yjg1YyBcdWNkMWQgJDYkXHVhYzFjXHViMmU0LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjMzNjk2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVURQIFN0cmluZyIsImRlc2NyaXB0aW9uIjoiPHA+QSBzdHJpbmcgaXMgY2FsbGVkIGEgPHN0cm9uZz5VRFAgc3RyaW5nPFwvc3Ryb25nPiBpZiBpdCBjb25zaXN0cyBvbmx5IG9mIHRoZSBjaGFyYWN0ZXJzIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5VPFwvY29kZT48XC9zcGFuPiwgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPkQ8XC9jb2RlPjxcL3NwYW4+LCBhbmQmbmJzcDs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+UDxcL2NvZGU+PFwvc3Bhbj4sIGFuZCBjb250YWlucyBhbiBlcXVhbCBudW1iZXIgb2YgZWFjaCBvZiB0aGVzZSBjaGFyYWN0ZXJzLjxcL3A+XHJcblxyXG48cD5BbHNvLCBhIFVEUCBzdHJpbmcgdGhhdCBjYW5ub3QgYmUgY3JlYXRlZCBieSBjb25jYXRlbmF0aW5nIGFueSB0d28gVURQIHN0cmluZ3MgaXMgY2FsbGVkIGEgPHN0cm9uZz5jb21wbGV0ZSBVRFAgc3RyaW5nPFwvc3Ryb25nPi4gRm9yIGV4YW1wbGUsIHRoZSBzdHJpbmcgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPlVEUFBVRDxcL2NvZGU+PFwvc3Bhbj4gaXMgbm90IGEgY29tcGxldGUgVURQIHN0cmluZyBiZWNhdXNlIGl0IGNhbiBiZSBjcmVhdGVkIGJ5IGNvbmNhdGVuYXRpbmcmbmJzcDs8Y29kZT48c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+VURQIDxcL3NwYW4+PFwvY29kZT5hbmQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPlBVRDxcL2NvZGU+PFwvc3Bhbj4uJm5ic3A7IEhvd2V2ZXIsIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5VVUREUFAgPFwvY29kZT48XC9zcGFuPmlzIGEgY29tcGxldGUgVURQIHN0cmluZy48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYW4gaW50ZWdlciAkTiQsIGRldGVybWluZSB0aGUgbnVtYmVyIG9mIGNvbXBsZXRlIFVEUCBzdHJpbmdzIG9mIGxlbmd0aCAkM04kLiBTaW5jZSB0aGUgYW5zd2VyIG1heSBiZSBsYXJnZSwgb3V0cHV0IHRoZSByZXN1bHQgbW9kdWxvICQxMF45KzckLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciAkTiQsIGRlbm90aW5nIHRoZSBsZW5ndGggb2YgdGhlIFVEUCBzdHJpbmcsIGRpdmlkZWQgYnkgJDMkLiAoJDFcXGxlcSBOXFxsZXEgNVxcLDAwMCQpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgdGhlIG51bWJlciBvZiBjb21wbGV0ZSBVRFAgc3RyaW5ncyBvZiBsZW5ndGggJDNOJCBtb2R1bG8gJDEwXjkrNyQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5UaGVyZSBhcmUgJDYkIGNvbXBsZXRlIFVEUCBzdHJpbmdzIG9mIGxlbmd0aCAkMyQ6IDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5VRFA8XC9jb2RlPjxcL3NwYW4+LCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+VVBEPFwvY29kZT48XC9zcGFuPiwgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPkRVUDxcL2NvZGU+PFwvc3Bhbj4sIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5EUFU8XC9jb2RlPjxcL3NwYW4+LCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+UFVEPFwvY29kZT48XC9zcGFuPiwgYW5kIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5QRFU8XC9jb2RlPjxcL3NwYW4+LjxcL3A+XHJcbiJ9XQ==