Binary Ones Product

Given a positive integer N, compute the product:

$$\prod_{i=1}^{N}\text{sum}(i)$$

where \(\text{sum}(i)\) denotes the number of ones in the binary representation of i. For example, when N = 3, we have:

$$\text{sum}(1)=1, \quad \text{sum}(2)=1, \quad \text{sum}(3)=2$$

Thus, the product is 1 * 1 * 2 = 2.

inputFormat

The input consists of a single positive integer N.

outputFormat

Output the computed product: $$\prod_{i=1}^{N}\text{sum}(i)$$.

sample

1

1