시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 225 33 28 28.571%

문제

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

이항계수는 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+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjYjBcdWFjZmNcdWFjMDAgbVx1Yzc3OCBcdWM3NzRcdWQ1NmQgXHVhY2M0XHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjJlNFx1Yzc0Y1x1YzkwNFx1YmQ4MFx1ZDEzMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBuLGsgXHVjMzBkXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1YjI5NCBuXHVjNzc0IFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWMsIFx1YWMxOVx1Yzc0NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQga1x1YWMwMCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNjUxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmlub21pYWwgY29lZmZpY2llbnRzIiwiZGVzY3JpcHRpb24iOiI8cD5HdW5uYXIgaXMgcXVpdGUgYW4gb2xkIGFuZCBmb3JnZXRmdWwgcmVzZWFyY2hlci4gUmlnaHQgbm93IGhlIGlzIHdyaXRpbmcgYSBwYXBlciBvbiBzZWN1cml0eSBpbiBzb2NpYWwgbmV0d29ya3MgYW5kIGl0IGFjdHVhbGx5IGludm9sdmVzIHNvbWUgY29tYmluYXRvcmljcy4gSGUgd3JvdGUgYSBwcm9ncmFtIGZvciBjYWxjdWxhdGluZyBiaW5vbWlhbCBjb2VmXHVmYjAxY2llbnRzIHRvIGhlbHAgaGltIGNoZWNrIHNvbWUgb2YgaGlzIGNhbGN1bGF0aW9ucy48XC9wPlxyXG5cclxuPHA+QSBiaW5vbWlhbCBjb2VmXHVmYjAxY2llbnQgaXMgYSBudW1iZXI8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9kYXVtX2VxdWF0aW9uXzEzNTgzMDUyMTcwOTMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NjBweDsgb3BhY2l0eTowLjk7IHdpZHRoOjE3N3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPndoZXJlIG4gYW5kIGsgYXJlIG5vbi1uZWdhdGl2ZSBpbnRlZ2Vycy48XC9wPlxyXG5cclxuPHA+R3VubmFyIHVzZWQgaGlzIHByb2dyYW0gdG8gY2FsY3VsYXRlIGMobiwgaykgYW5kIGdvdCBhIG51bWJlciBtIGFzIGEgcmVzdWx0LiBVbmZvcnR1bmF0ZWx5LCBzaW5jZSBoZSBpcyBmb3JnZXRmdWwsIGhlIGZvcmdvdCB0aGUgbnVtYmVycyBuIGFuZCBrIGhlIHVzZWQgYXMgaW5wdXQuIFRoZXNlIHR3byBudW1iZXJzIHdlcmUgYSByZXN1bHQgb2YgYSBsb25nIGNhbGN1bGF0aW9uIGFuZCB0aGV5IGFyZSB3cml0dGVuIG9uIG9uZSBvZiBtYW55IHBhcGVycyBseWluZyBvbiBoaXMgZGVzay4gSW5zdGVhZCBvZiB0cnlpbmcgdG8gc2VhcmNoIGZvciB0aGUgcGFwZXJzLCBoZSB0cmllZCB0byByZWNvbnN0cnVjdCB0aGUgbnVtYmVycyBuLCBrIGZyb20gdGhlIG91dHB1dCBoZSBnb3QuIENhbiB5b3UgaGVscCBoaW0gYW5kIFx1ZmIwMW5kIGFsbCBwb3NzaWJsZSBjYW5kaWRhdGVzPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIGZpcnN0IGxpbmUgYSBwb3NpdGl2ZSBpbnRlZ2VyOiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIG0gKDIgJmxlOyBtICZsZTsgMTA8c3VwPjE1PFwvc3VwPik6IHRoZSBvdXRwdXQgb2YgR3VubmFyJnJzcXVvO3MgcHJvZ3JhbS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhbiBpbnRlZ2VyOiB0aGUgbnVtYmVyIG9mIHdheXMgb2YgZXhwcmVzc2luZyBtIGFzIGEgYmlub21pYWwgY29lZlx1ZmIwMWNpZW50LjxcL2xpPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGFsbCBwYWlycyAobiwgaykgdGhhdCBzYXRpc2Z5IGMobiwgaykgPSBtLiBPcmRlciB0aGVtIGluIGluY3JlYXNpbmcgb3JkZXIgb2YgbiBhbmQsIGluIGNhc2Ugb2YgYSB0aWUsIG9yZGVyIHRoZW0gaW4gaW5jcmVhc2luZyBvcmRlciBvZiBrLiBGb3JtYXQgdGhlbSBhcyBpbiB0aGUgc2FtcGxlIG91dHB1dC48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==