Summation of Logarithms of Lowbit Products

Given an integer n, compute the following sum:

$$S=\sum_{i=1}^{2^{n}} \log_{2}\Bigl(\prod_{j=1}^{i}\text{lowbit}(j)\Bigr)$$

Here, for any positive integer x, lowbit(x) is defined as the largest power of 2 that divides x. Equivalently, lowbit(x)=x & (-x).

Hint: Note that for any positive integer j, lowbit(j) is of the form $$2^{v_2(j)}$$ where $$v_2(j)$$ is the exponent of 2 in the prime factorization of j (i.e. the number of trailing zeros in the binary representation of j). Therefore,

$$\log_{2}\Bigl(\prod_{j=1}^{i}\text{lowbit}(j)\Bigr)=\sum_{j=1}^{i} v_2(j).$$

One may show that $$\sum_{j=1}^{i} v_2(j)=i- s_2(i),$$ where $$s_2(i)$$ is the sum of the binary digits of i. Thus the original summation can be rewritten as:

$$S=\sum_{i=1}^{2^{n}} (i-s_2(i)).$$

Moreover, using known formulas, it can be derived that:

$$S = 2^{n-1}(2^n+1-n)-1.$$

Your task is to implement a program that reads the integer n and outputs the computed value of S.

inputFormat

The input consists of a single integer n (where n ≥ 1).

outputFormat

Output a single integer, the value of
$$S = \sum_{i=1}^{2^{n}} \log_{2}\Bigl(\prod_{j=1}^{i}\text{lowbit}(j)\Bigr)$$ which is equal to
$$2^{n-1}(2^n+1-n)-1.$$

sample

1

1