파스칼 삼각형

파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다.

단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다.

1. $i$ 번째 행에는 $i$개의 수가 있다.
2. 첫 번째 행은 $1$이다.
3. 두 번째 행부터, 각 행의 양 끝의 값은 $1$이고, 나머지 수의 값은 바로 위 행의 인접한 두 수의 합이다.

[ 다섯 번째 행까지의 파스칼의 삼각형 ]

여기서 파스칼의 삼각형이 $N$번째 행까지 존재할 때 인접한 두 수의 차이의 최댓값과 최댓값을 만들 수 있는 쌍의 개수를 구하려고 한다.

여기에서 인접한다는 것은 같은 행에서 인접한 두 수이거나 위 행과 아래 행에서 대각선으로 인접한 것도 인접한다고 본다.

다시 말하자면, $i$번째 행의 $j$번째 수를 $P_{i, j}$ 라고 한다면 $P_{i, j}$와 인접한 항들은

• 같은 행: $P_{i, j-1}$, $P_{i, j+1}$
• $i - 1$번째 행: $P_{i-1, j-1}$, $P_{i-1, j}$
• $i + 1$번째 행: $P_{i+1, j}$, $P_{i+1, j+1}$

이렇게 정리할 수 있다.

인접한 두 수의 차이의 최댓값을 $10^{9}+7$로 나눈 나머지와 그 최댓값을 만들 수 있는 쌍의 개수를 구해보자.

행의 수 $N$이 주어진다. $(2 \leq N \leq 4\,000\,000)$

인접한 두 수의 차이의 최댓값을 $10^{9}+7$로 나눈 나머지와 쌍의 개수를 공백으로 구분하여 출력한다.