시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 299 103 81 33.061%

문제

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
W3sicHJvYmxlbV9pZCI6IjMwMzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2M2NcdWI3ODAiLCJkZXNjcmlwdGlvbiI6IlxyXG48cD5cclxuXHROXHVhYzFjXHVjNzU4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc0MCAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHVjNzkwXHVjNWYwXHVjMjE4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWMwMSBcdWMyMmJcdWM3OTBcdWIyOTQgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWI0ZjFcdWM3YTVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWNlMCwgXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjIFx1YjM1NCBcdWJhM2NcdWM4MDAgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWMzMGRcdWM3NDQgXHVkNjNjXHViM2M4XHVjNzU4IFx1YzMwZFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWQ2M2NcdWI3ODBcdWIzYzRcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1ZDYzY1x1YjNjOFx1Yzc1OCBcdWMzMGRcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAoMSwgNCwgMywgMilcdWM3NTggXHVkNjNjXHViNzgwXHViM2M0XHViMjk0IDNcdWM3NzRcdWIyZTQuIFx1YWRmOCBcdWM3NzRcdWM3MjBcdWIyOTQgXHVkNjNjXHViM2M4XHVjNzU4IFx1YzMwZFx1Yzc3NCAoNCwgMyksICg0LCAyKSwgKDMsIDIpXHViODVjIFx1YzEzOCBcdWFjMWMgXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0Tlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWQ2M2NcdWI3ODBcdWIzYzRcdWFjMDAgQ1x1Yzc3OCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDAwLCAwICZsZTsgQyAmbGU7IDEwMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNjNjXHViNzgwXHViM2M0XHVhYzAwIENcdWM3NzRcdWFjZTAgXHVhZTM4XHVjNzc0XHVhYzAwIE5cdWM3NzggXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyAxLDAwMCwwMDAsMDA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwMzciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJaQlJLQSIsImRlc2NyaXB0aW9uIjoiPHA+Q29uc2lkZXIgYSBzZXF1ZW5jZSBvZiBOIGludGVnZXJzIHdoZXJlIGVhY2ggaW50ZWdlciBiZXR3ZWVuIDEgYW5kIE4gYXBwZWFycyBleGFjdGx5IG9uY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkEgcGFpciBvZiBudW1iZXJzIGluIHRoZSBzZXF1ZW5jZSBpcyBjb25mdXNlZCBpZiB0aGUgbnVtYmVyIHRoYXQgY29tZXMgZWFybGllciBpbiB0aGUgc2VxdWVuY2UgaXMgbGFyZ2VyIHRoYW4gdGhlIGxhdGVyIG51bWJlci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGNvbmZ1c2lvbiBvZiB0aGUgc2VxdWVuY2UgaXMgdGhlIG51bWJlciBvZiBjb25mdXNlZCBwYWlycyBpbiBpdC4gRm9yIGV4YW1wbGUsIHRoZSBjb25mdXNpb24gb2YgdGhlIHNlcXVlbmNlICgxLCA0LCAzLCAyKSBpcyAzIGJlY2F1c2UgdGhlcmUgYXJlIDMgY29uZnVzZWQgcGFpcnM6ICg0LCAzKSwgKDQsIDIpIGFuZCAoMywgMikuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXMgdGhlIG51bWJlciBvZiBzZXF1ZW5jZXMgb2YgbGVuZ3RoIE4gd2hvc2UgY29uZnVzaW9uIGlzIGV4YWN0bHkgQy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycywgTiAoMSAmbGU7IE4gJmxlOyAxMDAwKSBhbmQgQyAoMCAmbGU7IEMgJmxlOyAxMDAwMCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbnVtYmVyIG9mIHNlcXVlbmNlcyBtb2R1bG8gMTAwMDAwMDAwNy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d