Binomial Coefficient

The binomial coefficient is the number of ways to choose $k$ items from $n$ distinct items without regard to order, and is defined as follows.

$\binom{n}{k} = \frac{n!}{k!\,(n-k)!} \quad (0 \le k \le n)$

Two people play a binomial-coefficient guessing game. One says an integer $m$, and the other must find every pair of integers $(n, k)$ such that $\binom{n}{k} = m$. For example, if $m = 15$, then $\binom{6}{2}$, $\binom{6}{4}$, $\binom{15}{1}$, and $\binom{15}{14}$ all equal $15$, so the answer is $(6, 2)$, $(6, 4)$, $(15, 1)$, $(15, 14)$.

Given an integer $m$, write a program that finds all pairs $(n, k)$ satisfying $\binom{n}{k} = m$. For every $m$ in the input, at least one such binomial coefficient exists.

The first line contains an integer $m$. ($2 \le m \le 10^{15}$)

On the first line, print the number of pairs $(n, k)$ satisfying $\binom{n}{k} = m$. On each of the following lines, print one pair: $n$ and $k$ separated by a space. Print the pairs in increasing order of $n$; when $n$ is equal, in increasing order of $k$.