시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 411 55 42 30.882%

문제

창영이와 강산이는 이항계수를 좋아한다. 창영이와 강산이는 집 방향이 같기 때문에, 같이 지하철을 타고 이항계수 맞추기 게임을 하면서 등하교를 한다.

이항계수는 n개의 서로 다른 물건 중에서 순서 없이 k개를 뽑는 조합의 가짓수이고, 다음과 같이 정의된다.

이항계수 게임은 창영이가 어떤 정수 m을 말하면, 강산이는 결과가 m인 n과 k를 생각한 뒤, 그것을 말하는 방식으로 이루어진다. 예를 들어, 창영이가 15라고 말했다면, 강산이는 (6,2), (6,4), (15,1), (15,14)를 말하면 된다.

창영이는 집에서 미리 이항계수를 계산해보고 나오기 때문에, 결과가 m인 이항계수는 적어도 하나 있다.

입력

첫째 줄에 m이 주어진다. (2 ≤ m ≤ 1015)

출력

첫째 줄에 결과가 m인 이항 계수의 개수를 출력한다. 다음줄부터 한 줄에 하나씩 n,k 쌍을 출력한다. 출력하는 순서는 n이 증가하는 순서, 같을 경우에는 k가 증가하는 순서대로 출력한다. 

예제 입력 1

15

예제 출력 1

4
6 2
6 4
15 1
15 14
W3sicHJvYmxlbV9pZCI6IjM2NTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWQ1NmRcdWFjYzRcdWMyMTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Y2MzZFx1YzYwMVx1Yzc3NFx1YzY0MCBcdWFjMTVcdWMwYjBcdWM3NzRcdWIyOTQgXHVjNzc0XHVkNTZkXHVhY2M0XHVjMjE4XHViOTdjIFx1Yzg4Ylx1YzU0NFx1ZDU1Y1x1YjJlNC4gXHVjYzNkXHVjNjAxXHVjNzc0XHVjNjQwIFx1YWMxNVx1YzBiMFx1Yzc3NFx1YjI5NCBcdWM5ZDEgXHViYzI5XHVkNWE1XHVjNzc0IFx1YWMxOVx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YWMxOVx1Yzc3NCBcdWM5YzBcdWQ1NThcdWNjYTBcdWM3NDQgXHVkMGMwXHVhY2UwIFx1Yzc3NFx1ZDU2ZFx1YWNjNFx1YzIxOCBcdWI5ZGVcdWNkOTRcdWFlMzAgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YmE3NFx1YzExYyBcdWI0ZjFcdWQ1NThcdWFkNTBcdWI5N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1Yzc3NFx1ZDU2ZFx1YWNjNFx1YzIxOFx1YjI5NCBuXHVhYzFjXHVjNzU4IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViYjNjXHVhYzc0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWMyMWNcdWMxMWMgXHVjNWM2XHVjNzc0IGtcdWFjMWNcdWI5N2MgXHViZjUxXHViMjk0IFx1Yzg3MFx1ZDU2OVx1Yzc1OCBcdWFjMDBcdWM5ZDNcdWMyMThcdWM3NzRcdWFjZTAsIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjODE1XHVjNzU4XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZGF1bV9lcXVhdGlvbl8xMzU4MzA1MjE3MDkzLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjYwcHg7IHdpZHRoOjE3N3B4XCIgXC8+PFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHVjNzc0XHVkNTZkXHVhY2M0XHVjMjE4IFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWNjM2RcdWM2MDFcdWM3NzRcdWFjMDAgXHVjNWI0XHViNWE0IFx1YzgxNVx1YzIxOCBtXHVjNzQ0IFx1YjlkMFx1ZDU1OFx1YmE3NCwgXHVhYzE1XHVjMGIwXHVjNzc0XHViMjk0IFx1YWNiMFx1YWNmY1x1YWMwMCBtXHVjNzc4IG5cdWFjZmMga1x1Yjk3YyBcdWMwZGRcdWFjMDFcdWQ1NWMgXHViNGE0LCBcdWFkZjhcdWFjODNcdWM3NDQgXHViOWQwXHVkNTU4XHViMjk0IFx1YmMyOVx1YzJkZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YWMwMCAxNVx1Yjc3Y1x1YWNlMCBcdWI5ZDBcdWQ1ODhcdWIyZTRcdWJhNzQsIFx1YWMxNVx1YzBiMFx1Yzc3NFx1YjI5NCAoNiwyKSwgKDYsNCksICgxNSwxKSwgKDE1LDE0KVx1Yjk3YyBcdWI5ZDBcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM5ZDFcdWM1ZDBcdWMxMWMgXHViYmY4XHViOWFjIFx1Yzc3NFx1ZDU2ZFx1YWNjNFx1YzIxOFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NzRcdWJjZjRcdWFjZTAgXHViMDk4XHVjNjI0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVhY2IwXHVhY2ZjXHVhYzAwIG1cdWM3NzggXHVjNzc0XHVkNTZkXHVhY2M0XHVjMjE4XHViMjk0IFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NThcdWIwOTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiXHJcblxyXG48cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IG0gJmxlOyAxMDxzdXA+MTU8XC9zdXA+KTxcL3A+XHJcblxyXG5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjYjBcdWFjZmNcdWFjMDAgbVx1Yzc3OCBcdWM3NzRcdWQ1NmQgXHVhY2M0XHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjJlNFx1Yzc0Y1x1YzkwNFx1YmQ4MFx1ZDEzMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBuLGsgXHVjMzBkXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1YjI5NCBuXHVjNzc0IFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWMsIFx1YWMxOVx1Yzc0NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQga1x1YWMwMCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM2NTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCaW5vbWlhbCBjb2VmZmljaWVudHMiLCJkZXNjcmlwdGlvbiI6IjxwPkd1bm5hciBpcyBxdWl0ZSBhbiBvbGQgYW5kIGZvcmdldGZ1bCByZXNlYXJjaGVyLiBSaWdodCBub3cgaGUgaXMgd3JpdGluZyBhIHBhcGVyIG9uIHNlY3VyaXR5IGluIHNvY2lhbCBuZXR3b3JrcyBhbmQgaXQgYWN0dWFsbHkgaW52b2x2ZXMgc29tZSBjb21iaW5hdG9yaWNzLiBIZSB3cm90ZSBhIHByb2dyYW0gZm9yIGNhbGN1bGF0aW5nIGJpbm9taWFsIGNvZWZcdWZiMDFjaWVudHMgdG8gaGVscCBoaW0gY2hlY2sgc29tZSBvZiBoaXMgY2FsY3VsYXRpb25zLjxcL3A+XHJcblxyXG48cD5BIGJpbm9taWFsIGNvZWZcdWZiMDFjaWVudCBpcyBhIG51bWJlcjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2RhdW1fZXF1YXRpb25fMTM1ODMwNTIxNzA5My5wbmdcIiBzdHlsZT1cImhlaWdodDo2MHB4OyBvcGFjaXR5OjAuOTsgd2lkdGg6MTc3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+d2hlcmUgbiBhbmQgayBhcmUgbm9uLW5lZ2F0aXZlIGludGVnZXJzLjxcL3A+XHJcblxyXG48cD5HdW5uYXIgdXNlZCBoaXMgcHJvZ3JhbSB0byBjYWxjdWxhdGUgYyhuLCBrKSBhbmQgZ290IGEgbnVtYmVyIG0gYXMgYSByZXN1bHQuIFVuZm9ydHVuYXRlbHksIHNpbmNlIGhlIGlzIGZvcmdldGZ1bCwgaGUgZm9yZ290IHRoZSBudW1iZXJzIG4gYW5kIGsgaGUgdXNlZCBhcyBpbnB1dC4gVGhlc2UgdHdvIG51bWJlcnMgd2VyZSBhIHJlc3VsdCBvZiBhIGxvbmcgY2FsY3VsYXRpb24gYW5kIHRoZXkgYXJlIHdyaXR0ZW4gb24gb25lIG9mIG1hbnkgcGFwZXJzIGx5aW5nIG9uIGhpcyBkZXNrLiBJbnN0ZWFkIG9mIHRyeWluZyB0byBzZWFyY2ggZm9yIHRoZSBwYXBlcnMsIGhlIHRyaWVkIHRvIHJlY29uc3RydWN0IHRoZSBudW1iZXJzIG4sIGsgZnJvbSB0aGUgb3V0cHV0IGhlIGdvdC4gQ2FuIHlvdSBoZWxwIGhpbSBhbmQgXHVmYjAxbmQgYWxsIHBvc3NpYmxlIGNhbmRpZGF0ZXM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBhIHBvc2l0aXZlIGludGVnZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGFuIGludGVnZXIgbSAoMiAmbGU7IG0gJmxlOyAxMDxzdXA+MTU8XC9zdXA+KTogdGhlIG91dHB1dCBvZiBHdW5uYXImcnNxdW87cyBwcm9ncmFtLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGFuIGludGVnZXI6IHRoZSBudW1iZXIgb2Ygd2F5cyBvZiBleHByZXNzaW5nIG0gYXMgYSBiaW5vbWlhbCBjb2VmXHVmYjAxY2llbnQuPFwvbGk+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYWxsIHBhaXJzIChuLCBrKSB0aGF0IHNhdGlzZnkgYyhuLCBrKSA9IG0uIE9yZGVyIHRoZW0gaW4gaW5jcmVhc2luZyBvcmRlciBvZiBuIGFuZCwgaW4gY2FzZSBvZiBhIHRpZSwgb3JkZXIgdGhlbSBpbiBpbmNyZWFzaW5nIG9yZGVyIG9mIGsuIEZvcm1hdCB0aGVtIGFzIGluIHRoZSBzYW1wbGUgb3V0cHV0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=