Maximal Perfect Subsequence Sum

A subsequence of a sequence is obtained by taking some elements (possibly not contiguous) in the original order. The value of a subsequence is defined as the sum of its elements.

A sequence is called a perfect sequence if it is strictly decreasing and, in addition, every element (except the first) is a divisor of its immediate predecessor. In other words, a sequence \(a_1,a_2,\dots,a_k\) is perfect if \[ a_1 > a_2 > \cdots > a_k \quad \text{and} \quad \forall\, 2\le i\le k,\; a_{i-1}\equiv 0\; (\bmod\; a_i). \]

For any sequence, a perfect subsequence is a subsequence which is a perfect sequence. The length of the longest perfect subsequence of a sequence is called its perfect length.

Given a positive integer \(n\), consider all permutations of the numbers \(1,2,\dots,n\). Define the n-th maximum perfect length as the maximum perfect length among all these permutations. It turns out that this maximum length is always \[ T = \lfloor \log_{2}(n) \rfloor + 1. \]

Your task is: For the given \(n\), output the sum of the values (i.e. the sum of the elements in the subsequence) of all perfect subsequences (from all permutations of \(1,2,\dots,n\)) that have length exactly \(T\). Note that a perfect subsequence is considered only in those permutations that obtain the maximal perfect length \(T\); if a permutation has a maximum perfect length less than \(T\) then it does not contribute.

The key observation is that for any fixed perfect sequence \(s = (a_1,a_2,\dots,a_T)\) satisfying \[ a_1 > a_2 > \cdots > a_T \quad \text{and} \quad \forall\, 2\le i\le T,\; a_{i-1}\equiv 0\; (\bmod\; a_i), \quad a_i \in \{1,2,\dots,n\}, \] this sequence appears as a subsequence in exactly \(\frac{n!}{T!}\) of the permutations. Hence, if \(S\) is the set of all valid perfect sequences of length \(T\) and if \(\text{sum}(s)\) denotes the sum of the elements in \(s\), then the final answer is \[ \frac{n!}{T!}\cdot\sum_{s\in S} \text{sum}(s). \]

You are required to compute and output this final sum.

inputFormat

The input consists of a single integer \(n\) (\(1 \le n \le \) small value) on one line.

outputFormat

Output a single integer which is the required sum.

sample

1

1