시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB86631322532.609%

문제

N개의 자연수로 이루어진 수열이 있다. 이 수열은 1부터 N까지 자연수로 이루어져 있으며, 각 숫자는 한 번씩 등장한다.

첫 번째 숫자가 두 번째 숫자보다 크고, 수열에서 더 먼저 등장하는 숫자의 쌍을 혼돈의 쌍이라고 한다.

수열의 혼란도는 수열의 혼돈의 쌍의 개수이다. 예를 들어, (1, 4, 3, 2)의 혼란도는 3이다. 그 이유는 혼돈의 쌍이 (4, 3), (4, 2), (3, 2)로 세 개 있기 때문이다.

N이 주어졌을 때, 혼란도가 C인 수열의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 C가 주어진다. (1 ≤ N ≤ 1000, 0 ≤ C ≤ 10000)

출력

첫째 줄에 혼란도가 C이고 길이가 N인 수열의 개수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

10 1

예제 출력 1

9

예제 입력 2

4 3

예제 출력 2

6

예제 입력 3

9 13

예제 출력 3

17957
W3sicHJvYmxlbV9pZCI6IjMwMzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2M2NcdWI3ODAiLCJkZXNjcmlwdGlvbiI6IjxwPk5cdWFjMWNcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVjMjE4XHVjNWY0XHVjNzQwIDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWM3OTBcdWM1ZjBcdWMyMThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhYzAxIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjRmMVx1YzdhNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWFjMDAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhY2UwLCBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHViMzU0IFx1YmEzY1x1YzgwMCBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTQgXHVjMjJiXHVjNzkwXHVjNzU4IFx1YzMwZFx1Yzc0NCBcdWQ2M2NcdWIzYzhcdWM3NTggXHVjMzBkXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMjE4XHVjNWY0XHVjNzU4IFx1ZDYzY1x1Yjc4MFx1YjNjNFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVkNjNjXHViM2M4XHVjNzU4IFx1YzMwZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICgxLCA0LCAzLCAyKVx1Yzc1OCBcdWQ2M2NcdWI3ODBcdWIzYzRcdWIyOTQgM1x1Yzc3NFx1YjJlNC4gXHVhZGY4IFx1Yzc3NFx1YzcyMFx1YjI5NCBcdWQ2M2NcdWIzYzhcdWM3NTggXHVjMzBkXHVjNzc0ICg0LCAzKSwgKDQsIDIpLCAoMywgMilcdWI4NWMgXHVjMTM4IFx1YWMxYyBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5OXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1ZDYzY1x1Yjc4MFx1YjNjNFx1YWMwMCBDXHVjNzc4IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMDAsIDAgJmxlOyBDICZsZTsgMTAwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ2M2NcdWI3ODBcdWIzYzRcdWFjMDAgQ1x1Yzc3NFx1YWNlMCBcdWFlMzhcdWM3NzRcdWFjMDAgTlx1Yzc3OCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIDEsMDAwLDAwMCwwMDdcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzAzNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlpCUktBIiwiZGVzY3JpcHRpb24iOiI8cD5Db25zaWRlciBhIHNlcXVlbmNlIG9mIE4gaW50ZWdlcnMgd2hlcmUgZWFjaCBpbnRlZ2VyIGJldHdlZW4gMSBhbmQgTiBhcHBlYXJzIGV4YWN0bHkgb25jZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBwYWlyIG9mIG51bWJlcnMgaW4gdGhlIHNlcXVlbmNlIGlzIGNvbmZ1c2VkIGlmIHRoZSBudW1iZXIgdGhhdCBjb21lcyBlYXJsaWVyIGluIHRoZSBzZXF1ZW5jZSBpcyBsYXJnZXIgdGhhbiB0aGUgbGF0ZXIgbnVtYmVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgY29uZnVzaW9uIG9mIHRoZSBzZXF1ZW5jZSBpcyB0aGUgbnVtYmVyIG9mIGNvbmZ1c2VkIHBhaXJzIGluIGl0LiBGb3IgZXhhbXBsZSwgdGhlIGNvbmZ1c2lvbiBvZiB0aGUgc2VxdWVuY2UgKDEsIDQsIDMsIDIpIGlzIDMgYmVjYXVzZSB0aGVyZSBhcmUgMyBjb25mdXNlZCBwYWlyczogKDQsIDMpLCAoNCwgMikgYW5kICgzLCAyKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgbnVtYmVyIG9mIHNlcXVlbmNlcyBvZiBsZW5ndGggTiB3aG9zZSBjb25mdXNpb24gaXMgZXhhY3RseSBDLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzLCBOICgxICZsZTsgTiAmbGU7IDEwMDApIGFuZCBDICgwICZsZTsgQyAmbGU7IDEwMDAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBudW1iZXIgb2Ygc2VxdWVuY2VzIG1vZHVsbyAxMDAwMDAwMDA3LiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #4 4번