문제
이 문제는 출근하기 싫어 2와 굵은 글씨로 적힌 부분과 제한 조건만 다릅니다.
누구나 그렇듯 동우는 출근하기 싫다. 그래도 출근해야 한다.
동우가 다니는 회사는 신기한 회사이다. 총 $N$명의 직원이 있는데, 이 중 최대 1ドル$명이 출근하지 않아도 업무를 정상적으로 진행할 수 있다. 하지만 1ドル$명보다 많이 출근하지 않으면 업무를 정상적으로 진행할 수 없다.
동우는 회사의 업무가 정상적으로 진행되는 것이 신기해 현재 시각으로부터 최근 $M$시간 동안 $N$명의 직원 각각이 총 몇 시간씩 출근했는지 살펴보았다.
직원들은 모두 정각에만 출근해 정각에만 퇴근하며, 한 사람이 여러 번 출근 혹은 퇴근할 수 있다. 최근 $M$시간 동안 업무를 계속 정상적으로 진행할 수 있도록 하는, $N$명의 직원이 출근한 조합의 경우의 수를 구하시오.
이때, $M$시간에 대해 매시 30분을 기준으로 출근해 있는 직원들의 목록이 한 번이라도 다른 경우 서로 다른 조합으로 간주한다. 현재는 정각이라 가정한다.
출력
직원이 출근한 조합으로 가능한 경우의 수를 10ドル^9+7$로 나눈 나머지를 출력한다.
단, 10ドル^9+7$은 소수이다.
서브태스크
| 번호 | 배점 | 제한 | | 1 | 21 | $N\times M \le 20$
|
| 2 | 24 | $N, M \le 6$
|
| 3 | 64 | $N, M \le 1000$
|
| 4 | 71 | 추가적인 제한 조건 없음
|
W3sicHJvYmxlbV9pZCI6IjMxNTM3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjZDljXHVhZGZjXHVkNTU4XHVhZTMwIFx1YzJlYlx1YzViNCAxIiwiZGVzY3JpcHRpb24iOiI8YmxvY2txdW90ZT5cclxuPHA+XHVjNzc0IFx1YmIzOFx1YzgxY1x1YjI5NCA8YSBocmVmPVwiXC9wcm9ibGVtXC8zMTUzOFwiPlx1Y2Q5Y1x1YWRmY1x1ZDU1OFx1YWUzMCBcdWMyZWJcdWM1YjQgMjxcL2E+XHVjNjQwIDxzdHJvbmc+XHVhZDc1XHVjNzQwPFwvc3Ryb25nPiBcdWFlMDBcdWM1MjhcdWI4NWMgXHVjODAxXHVkNzhjIFx1YmQ4MFx1YmQ4NFx1YWNmYyBcdWM4MWNcdWQ1NWMgXHVjODcwXHVhYzc0XHViOWNjIFx1YjJlNFx1Yjk4NVx1YjJjOFx1YjJlNC48XC9wPlxyXG48XC9ibG9ja3F1b3RlPlxyXG5cclxuPHA+XHViMjA0XHVhZDZjXHViMDk4IFx1YWRmOFx1YjgwN1x1YjRlZiBcdWIzZDlcdWM2YjBcdWIyOTQgXHVjZDljXHVhZGZjXHVkNTU4XHVhZTMwIFx1YzJlYlx1YjJlNC4gXHVhZGY4XHViNzk4XHViM2M0IFx1Y2Q5Y1x1YWRmY1x1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNkOVx1YzZiMFx1YWMwMCBcdWIyZTRcdWIyYzhcdWIyOTQgXHVkNjhjXHVjMGFjXHViMjk0IFx1YzJlMFx1YWUzMFx1ZDU1YyBcdWQ2OGNcdWMwYWNcdWM3NzRcdWIyZTQuIFx1Y2QxZCAkTiRcdWJhODVcdWM3NTggXHVjOWMxXHVjNmQwXHVjNzc0IFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVjNzc0IFx1YzkxMSA8c3Ryb25nPlx1Y2Q1Y1x1YjMwMCAkMSRcdWJhODU8XC9zdHJvbmc+XHVjNzc0IFx1Y2Q5Y1x1YWRmY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NDRcdWIzYzQgXHVjNWM1XHViYjM0XHViOTdjIFx1YzgxNVx1YzBjMVx1YzgwMVx1YzczY1x1Yjg1YyBcdWM5YzRcdWQ1ODlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIDxzdHJvbmc+JDEkXHViYTg1XHViY2Y0XHViMmU0PFwvc3Ryb25nPiBcdWI5Y2VcdWM3NzQgXHVjZDljXHVhZGZjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NCBcdWM1YzVcdWJiMzRcdWI5N2MgXHVjODE1XHVjMGMxXHVjODAxXHVjNzNjXHViODVjIFx1YzljNFx1ZDU4OVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzZDlcdWM2YjBcdWIyOTQgXHVkNjhjXHVjMGFjXHVjNzU4IFx1YzVjNVx1YmIzNFx1YWMwMCBcdWM4MTVcdWMwYzFcdWM4MDFcdWM3M2NcdWI4NWMgXHVjOWM0XHVkNTg5XHViNDE4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWMyZTBcdWFlMzBcdWQ1NzQgXHVkNjA0XHVjN2FjIFx1YzJkY1x1YWMwMVx1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWNkNWNcdWFkZmMgJE0kXHVjMmRjXHVhYzA0IFx1YjNkOVx1YzU0OCAkTiRcdWJhODVcdWM3NTggXHVjOWMxXHVjNmQwIFx1YWMwMVx1YWMwMVx1Yzc3NCBcdWNkMWQgXHViYTg3IFx1YzJkY1x1YWMwNFx1YzUyOSBcdWNkOWNcdWFkZmNcdWQ1ODhcdWIyOTRcdWM5YzAgXHVjMGI0XHVkM2I0XHViY2Y0XHVjNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5YzFcdWM2ZDBcdWI0ZTRcdWM3NDAgXHViYWE4XHViNDUwIFx1YzgxNVx1YWMwMVx1YzVkMFx1YjljYyBcdWNkOWNcdWFkZmNcdWQ1NzQgXHVjODE1XHVhYzAxXHVjNWQwXHViOWNjIFx1ZDFmNFx1YWRmY1x1ZDU1OFx1YmE3MCwgXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1Y2Q5Y1x1YWRmYyBcdWQ2MzlcdWM3NDAgXHVkMWY0XHVhZGZjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Y2Q1Y1x1YWRmYyAkTSRcdWMyZGNcdWFjMDQgXHViM2Q5XHVjNTQ4IFx1YzVjNVx1YmIzNFx1Yjk3YyBcdWFjYzRcdWMxOGQgXHVjODE1XHVjMGMxXHVjODAxXHVjNzNjXHViODVjIFx1YzljNFx1ZDU4OVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViM2M0XHViODVkIFx1ZDU1OFx1YjI5NCwgJE4kXHViYTg1XHVjNzU4IFx1YzljMVx1YzZkMFx1Yzc3NCBcdWNkOWNcdWFkZmNcdWQ1NWMgXHVjODcwXHVkNTY5XHVjNzU4IFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI1NGMsICRNJFx1YzJkY1x1YWMwNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHViOWU0XHVjMmRjIDMwXHViZDg0XHVjNzQ0IFx1YWUzMFx1YzkwMFx1YzczY1x1Yjg1YyBcdWNkOWNcdWFkZmNcdWQ1NzQgXHVjNzg4XHViMjk0IFx1YzljMVx1YzZkMFx1YjRlNFx1Yzc1OCBcdWJhYTlcdWI4NWRcdWM3NzQgXHVkNTVjIFx1YmM4OFx1Yzc3NFx1Yjc3Y1x1YjNjNCBcdWIyZTRcdWI5NzggXHVhY2JkXHVjNmIwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjODcwXHVkNTY5XHVjNzNjXHViODVjIFx1YWMwNFx1YzhmY1x1ZDU1Y1x1YjJlNC4gXHVkNjA0XHVjN2FjXHViMjk0IFx1YzgxNVx1YWMwMVx1Yzc3NFx1Yjc3YyBcdWFjMDBcdWM4MTVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM5YzFcdWM2ZDBcdWM3NTggXHVjMjE4ICROJFx1YWNmYyBcdWIzZDlcdWM2YjBcdWFjMDAgXHVjMGI0XHVkM2I0XHViY2Y4IFx1Y2Q1Y1x1YWRmYyBcdWMyZGNcdWFjMDRcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMTggJE0kXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDFcXGxlIE4sIE1cXGxlIDEwXjYpJDxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCAkTiRcdWJhODVcdWM3NTggXHVjOWMxXHVjNmQwXHVjNzc0IFx1Y2Q1Y1x1YWRmYyAkTSRcdWMyZGNcdWFjMDQgXHViM2Q5XHVjNTQ4IFx1Y2Q5Y1x1YWRmY1x1ZDU1YyBcdWMyZGNcdWFjMDQgJEFfMSwgQV8yLCBcXGNkb3RzLCBBX04kXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDBcXGxlIEFfaSBcXGxlIE0pJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzljMVx1YzZkMFx1Yzc3NCBcdWNkOWNcdWFkZmNcdWQ1NWMgXHVjODcwXHVkNTY5XHVjNzNjXHViODVjIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjICQxMF45KzckXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTgsICQxMF45KzckXHVjNzQwIFx1YzE4Y1x1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzdWJ0YXNrMSI6IjxwPiROXFx0aW1lcyBNIFxcbGUgMjAkPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD4kTiwgTSBcXGxlIDYkPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD4kTiwgTSBcXGxlIDEwMDAkPFwvcD5cclxuIiwic3VidGFzazQiOiI8cD5cdWNkOTRcdWFjMDBcdWM4MDFcdWM3NzggXHVjODFjXHVkNTVjIFx1Yzg3MFx1YWM3NCBcdWM1YzZcdWM3NGM8XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIzMTUzNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkkgZG9uXHUyMDE5dCB3YW5uYSBnbyB0byB3b3JrIDEiLCJkZXNjcmlwdGlvbiI6IjxibG9ja3F1b3RlPlxyXG48cD5UaGlzIHByb2JsZW0sIGNvbXBhcmVkIHRvIDxhIGhyZWY9XCJcL3Byb2JsZW1cLzMxNTM4XCI+SSBkb24mcnNxdW87dCB3YW5uYSBnbyB0byB3b3JrIDI8XC9hPiwgaXMgdGhlIHNhbWUgZXhjZXB0IGZvciB0aGUgPHN0cm9uZz5ib2xkPFwvc3Ryb25nPiBwYXJ0cyBhbmQgdGhlJm5ic3A7Y29uc3RyYWludHMgb2YgdGhlIHByb2JsZW0uPFwvcD5cclxuPFwvYmxvY2txdW90ZT5cclxuXHJcbjxwPkxpa2UgZXZlcnlvbmUgZWxzZSwgRG9uZ3dvbyBkb2VzbiZyc3F1bzt0IHdhbnQgdG8gZ28gdG8gd29yay4gU3RpbGwsIGhlIG11c3QuPFwvcD5cclxuXHJcbjxwPkRvbmd3b28mcnNxdW87cyBjb21wYW55IGlzIGEgcGVjdWxpYXIgb25lLiBUaGVyZSBhcmUgYSB0b3RhbCBvZiAkTiQgZW1wbG95ZWVzLCBhbmQgZXZlbiBpZiA8c3Ryb25nPnVwIHRvICQxJDxcL3N0cm9uZz4gb2YgdGhlbSBkb2VzbiZyc3F1bzt0IGNvbWUgdG8gd29yaywgdGhlIGNvbXBhbnkgY2FuIHN0aWxsIGNhcnJ5IG91dCBpdHMgYnVzaW5lc3Mgbm9ybWFsbHkuIEJ1dCBpZiA8c3Ryb25nPm1vcmUgdGhhbiAkMSQ8XC9zdHJvbmc+IHBlcnNvbiBkb2VzbiZyc3F1bzt0IGNvbWUgdG8gd29yaywgdGhlIGNvbXBhbnkgY2Fubm90IGNhcnJ5IG91dCBpdHMgYnVzaW5lc3Mgbm9ybWFsbHkuPFwvcD5cclxuXHJcbjxwPkRvbmd3b28sIHN1cnByaXNlZCB0aGF0IHRoZSBjb21wYW55JnJzcXVvO3Mgd29yayB3YXMgY2FycmllZCBvdXQgbm9ybWFsbHkgaW4gdGhlc2UgY29uZGl0aW9ucywgbG9va2VkIGF0IGhvdyBtYW55IGhvdXJzIGVhY2ggb2YgdGhlICROJCBlbXBsb3llZXMgd2VudCB0byB3b3JrIGluIHRoZSBsYXN0ICRNJCBob3Vycy48XC9wPlxyXG5cclxuPHA+RXZlcnlvbmUgZ29lcyB0byB3b3JrIGFuZCBnZXRzIG9mZiB3b3JrIGV4YWN0bHkgb24gdGhlIGhvdXIsIGFuZCB0aGUgY29tcGFueSB3YXMgYWJsZSB0byBjYXJyeSBvdXQgaXRzIGJ1c2luZXNzIG5vcm1hbGx5IGZvciB0aGUgbGFzdCAkTSQgaG91cnMuIEdpdmVuIHRoZSB0b3RhbCBudW1iZXIgb2YgaG91cnMgZWFjaCBvZiB0aGUgJE4kIGVtcGxveWVlcyBoYXMgZ29uZSB0byB3b3JrIGluIHRoZSBsYXN0ICRNJCBob3VycywgZmluZCB0aGUgbnVtYmVyIG9mIGFsbCBwb3NzaWJsZSBjYXNlcy4gQW4gZW1wbG95ZWUgY2FuIGdvIHRvIHdvcmsgb3IgZ2V0IG9mZiB3b3JrIHNldmVyYWwgdGltZXMuPFwvcD5cclxuXHJcbjxwPkluIHRoZSBwZXJpb2Qgb2YgJE0kIGhvdXJzLCBjaGVja2luZyBldmVyeSBob3VyIGF0IDMwIG1pbnV0ZXMgcGFzdCB0aGUgaG91ciwgaWYgdGhlcmUgaXMgYXQgbGVhc3Qgb25lIHRpbWUgd2hlcmUgYXQgbGVhc3Qgb25lIHBlcnNvbiB3aG8gd2VudCB0byB3b3JrIGlzIGRpZmZlcmVudCwgaXQgaXMgYSBkaWZmZXJlbnQgY2FzZS4gSXQgaXMgYXNzdW1lZCB0aGF0IHRoZSBjdXJyZW50IHRpbWUgaXMgb24gdGhlIGhvdXIuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMsICROJCBhbmQgJE0kLCBzZXBhcmF0ZWQgYnkgc3BhY2VzICQoMVxcbGUgTixNXFxsZSAxMF42KSQgJm5kYXNoOyB0aGUgbnVtYmVyIG9mIGVtcGxveWVlcyBhbmQgdGhlIGxlbmd0aCBvZiB0aGUgcmVjZW50IHRpbWUgRG9uZ3dvbyBsb29rZWQgYXQuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyAkTiQgaW50ZWdlcnMsICRBXzEsQV8yLFxcY2RvdHMgLEFfTiQsIHNlcGFyYXRlZCBieSBzcGFjZXMgJCgwXFxsZSBBX2lcXGxlIE0pJCAmbmRhc2g7IHRoZSB0aW1lIHRoZSBlbXBsb3llZXMgd2VudCB0byB3b3JrIGluIHRoZSBsYXN0ICRNJCBob3Vycy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgYSBzaW5nbGUgaW50ZWdlciAmbmRhc2g7IHRoZSByZW1haW5kZXIgb2YgdGhlIG51bWJlciBvZiBhbGwgcG9zc2libGUgY29tYmluYXRpb25zIG9mIGVtcGxveWVlcyB3aG8gd2VudCB0byB3b3JrLCBkaXZpZGVkIGJ5ICQxMF45KzckLjxcL3A+XHJcblxyXG48cD5Ob3RlIHRoYXQgJDEwXjkrNyQgaXMgYSBwcmltZSBudW1iZXIuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsInN1YnRhc2sxIjoiPHA+JE5cXHRpbWVzIE0gXFxsZSAyMCQ8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPiROLCBNIFxcbGUgNiQ8XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPiROLCBNIFxcbGUgMTAwMCQ8XC9wPlxyXG4iLCJzdWJ0YXNrNCI6IjxwPlRoZXJlIGFyZSBubyBhZGRpdGlvbmFsIHJlc3RyaWN0aW9ucy48XC9wPlxyXG4ifV0=