숙제

작은 헬레나는 얼마 전 초등학교 1학년을 마쳤다. 헬레나는 모범생이고 모든 과목에서 A를 받았으며 수학을 아주 좋아한다. 지금은 가족과 함께 보람찬 휴가를 보내고 있지만, 매일 하던 수학 숙제가 그리워지기 시작했다. 다행히 오빠가 헬레나의 지적 갈증을 채워 주기로 하고 다음 문제를 냈다.

유효한 식은 다음과 같이 재귀적으로 정의된다:

• 문자열 ?는 숫자를 나타내는 유효한 식이다.
• $A$와 $B$가 유효한 식이면 min(A,B)와 max(A,B)도 유효한 식이다. 여기서 min은 두 인자 중 작은 값을, max는 큰 값을 반환하는 함수를 나타낸다.

예를 들어 min(min(?,?),min(?,?))와 max(?,max(?,min(?,?)))는 위 정의에 따라 유효한 식이지만, ??, max(min(?)), min(?,?,?)는 유효한 식이 아니다.

헬레나는 물음표를 $N$개 포함한 유효한 식을 받았다. 각 물음표는 $\{1, 2, \dots, N\}$ 중 한 수로 바꾸되, 이 집합의 수가 식에 정확히 한 번씩 나타나도록 바꾼다. 즉, 물음표들은 1부터 $N$까지 수들의 순열로 바뀐다.

물음표를 수로 모두 바꾸면 식을 계산할 수 있고, 그 값은 1 이상 $N$ 이하의 정수가 된다. 물음표에 수를 배정하는 모든 방법을 고려할 때, 헬레나가 식을 계산해서 얻을 수 있는 서로 다른 값은 몇 개인가?

첫 번째이자 유일한 줄에 유효한 식이 주어진다.

1 이상 $N$ 이하의 정수 하나를 출력한다. 식을 계산하여 얻을 수 있는 서로 다른 값의 개수이다.

모든 소문제에서 $2 \le N \le 1\,000\,000$이다.