문제
알고리즘 기말고사는 용어와 정의를 선으로 연결하는 문제만 나온다. 왼쪽에는 용어 N개, 오른쪽에는 정의 N개가 한 줄로 나열되어 있다. 학생들은 각 용어에 해당하는 정의를 선으로 그려야 한다.
선영이는 자신의 뛰어난 프로그래밍 실력을 믿고 공부를 하지 않았다. 하지만, 기말고사는 프로그래밍 실력과 관계없는 문제만 나왔다. 따라서, 선영이는 문제를 모두 찍으려고 한다.
S(N,k)를 선영이가 문제를 모두 풀었을 때, 적어도 위에서부터 처음 k개 용어는 반드시 틀리는 경우의 수라고 하자.
N과 k가 주어졌을 때, S(N,k)를 구하는 프로그램을 작성하시오.
출력
각 테스트 케이스 마다 테스트 케이스 번호와 S(N,k)를 출력한다.
예제 출력 1
1 18
2 3216
3 2170680
4 130850092279664
W3sicHJvYmxlbV9pZCI6Ijk0NzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NGNcdWFjZTBcdWI5YWNcdWM5OTggXHVhZTMwXHViOWQwXHVhY2UwXHVjMGFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NGNcdWFjZTBcdWI5YWNcdWM5OTggXHVhZTMwXHViOWQwXHVhY2UwXHVjMGFjXHViMjk0IFx1YzZhOVx1YzViNFx1YzY0MCBcdWM4MTVcdWM3NThcdWI5N2MgXHVjMTIwXHVjNzNjXHViODVjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWJiMzhcdWM4MWNcdWI5Y2MgXHViMDk4XHVjNjI4XHViMmU0LiBcdWM2N2NcdWNhYmRcdWM1ZDBcdWIyOTQgXHVjNmE5XHVjNWI0IE5cdWFjMWMsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMFx1YjI5NCBcdWM4MTVcdWM3NTggTlx1YWMxY1x1YWMwMCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1YjA5OFx1YzVmNFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWFjMDEgXHVjNmE5XHVjNWI0XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWM4MTVcdWM3NThcdWI5N2MgXHVjMTIwXHVjNzNjXHViODVjIFx1YWRmOFx1YjgyNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHViNmYwXHVjNWI0XHViMDljIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1Yjc5OFx1YmMwZCBcdWMyZTRcdWI4MjVcdWM3NDQgXHViYmZmXHVhY2UwIFx1YWNmNVx1YmQ4MFx1Yjk3YyBcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTU4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YWUzMFx1YjlkMFx1YWNlMFx1YzBhY1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGQgXHVjMmU0XHViODI1XHVhY2ZjIFx1YWQwMFx1YWNjNFx1YzVjNlx1YjI5NCBcdWJiMzhcdWM4MWNcdWI5Y2MgXHViMDk4XHVjNjU0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWJiMzhcdWM4MWNcdWI5N2MgXHViYWE4XHViNDUwIFx1Y2MwZFx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlMoTixrKVx1Yjk3YyBcdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHViYjM4XHVjODFjXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWQ0ODBcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVjNzA0XHVjNWQwXHVjMTFjXHViZDgwXHVkMTMwIFx1Y2M5OFx1Yzc0YyBrXHVhYzFjIFx1YzZhOVx1YzViNFx1YjI5NCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVkMmMwXHViOWFjXHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48cD5OXHVhY2ZjIGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgUyhOLGspXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjODhcdWQ2MzhcdWM2NDAmbmJzcDtcdWI0NTAgXHVjODE1XHVjMjE4IE5cdWFjZmMga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDE3LCAwICZsZTsgayAmbGU7IE4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViOWM4XHViMmU0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViYzg4XHVkNjM4XHVjNjQwIFMoTixrKVx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiOTQ3MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRlcmFuZ2VkIEV4YW1zIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgZmlyc3QgcXVlc3Rpb24gb24gdGhlIERhdGEgU3RydWN0dXJlcyBhbmQgQWxnb3JpdGhtcyBmaW5hbCBleGFtIGhhcyBhIGxpc3Qgb2YgTiB0ZXJtcyBhbmQgYSBzZWNvbmQgbGlzdCBvZiBOIGRlZmluaXRpb25zLiBTdHVkZW50cyBhcmUgdG8gbWF0Y2ggZWFjaCB0ZXJtIHdpdGggdGhlIGNvcnJlY3QgZGVmaW5pdGlvbi48XC9wPlxyXG5cclxuPHA+VW5mb3J0dW5hdGVseSwgSm9lLCB3aG8gd3JvdGUgYSBWaXN1YWwgQkFTSUMgcHJvZ3JhbSBpbiBoaWdoIHNjaG9vbCBhbmQgYXNzdW1lZCBoZSBrbmV3IGFsbCB0aGVyZSB3YXMgdG8ga25vdyBhYm91dCBDb21wdXRlciBTY2llbmNlLCBkaWQgbm90IGJvdGhlciB0byBjb21lIHRvIGNsYXNzIG9yIHJlYWQgdGhlIHRleHRib29rLiBIZSBoYXMgdG8gZ3Vlc3MgcmFuZG9tbHkgd2hhdCB0aGUgbWF0Y2hlcyBhcmUuIExldCBTKE4saykgYmUgdGhlIG51bWJlciBvZiB3YXlzIEpvZSBjYW4gYW5zd2VyIHRoZSBxdWVzdGlvbiBhbmQgZ2V0IGF0IGxlYXN0IHRoZSBmaXJzdCBrIG1hdGNoZXMgd3JvbmcuPFwvcD5cclxuXHJcbjxwPkZvciB0aGlzIHByb2JsZW0sIHlvdSB3aWxsIHdyaXRlIGEgcHJvZ3JhbSB0byBjb21wdXRlIFMoTixrKS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgUCwgKDEgJmxlOyBQICZsZTsgMTAwMCksIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZGF0YSBzZXRzIHRoYXQgZm9sbG93LiBFYWNoIGRhdGEgc2V0IHNob3VsZCBiZSBwcm9jZXNzZWQgaWRlbnRpY2FsbHkgYW5kIGluZGVwZW5kZW50bHkuPFwvcD5cclxuXHJcbjxwPkVhY2ggZGF0YSBzZXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSBvZiBpbnB1dCBjb250YWluaW5nIHRocmVlIHNwYWNlIHNlcGFyYXRlZCBkZWNpbWFsIGludGVnZXJzLiBUaGUgZmlyc3QgaW50ZWdlciBpcyB0aGUgZGF0YSBzZXQgbnVtYmVyLiBUaGUgc2Vjb25kIGludGVnZXIgaXMgdGhlIG51bWJlciwgTiAoMSAmbGU7IE4gJmxlOyAxNyksIG9mIHRlcm1zIHRvIGJlIG1hdGNoZWQgaW4gdGhlIHF1ZXN0aW9uLiBUaGUgdGhpcmQgaW50ZWdlciBpcyB0aGUgbnVtYmVyLCBrICgwICZsZTsgayAmbGU7IE4pLCBvZiBpbml0aWFsIG1hdGNoZXMgdG8gYmUgaW5jb3JyZWN0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0IHRoZXJlIGlzIGEgc2luZ2xlIGxpbmUgb2Ygb3V0cHV0LiBJdCBjb250YWlucyB0aGUgZGF0YSBzZXQgbnVtYmVyIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIHNwYWNlIHdoaWNoIGlzIHRoZW4gZm9sbG93ZWQgYnkgdGhlIHZhbHVlIG9mIFMoTixrKS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d