16723번 - 원영이는 ZOAC과 영원하고 싶다

이름부터 영과일 그 자체인 원(1)영(0)이는 ZOAC의 운영진이다. 많은 학회원들이 ZOAC에 참가하기를 원했던 원영이는 ZOAC에 참가하는 모든 참가자들에게 기념품을 나누어주려고 한다. 이때 원영이는 참가자들이 상품 배분에 대해 불만을 가지지 않게 하면서 동시에 최대한 많은 참가자가 ZOAC에 참가할 수 있도록 하기 위해 다음과 같은 규칙들을 정하였다.

1. 제t회 ZOAC의 기념품 수는 2t개이다.
2. 참가자의 수는 2t개의 기념품을 남김없이 동일한 개수로 나누는 2의 거듭제곱이다.
3. 2번 조건을 만족하는 참가자의 수들 중 가장 큰 수가 제t회 ZOAC의 참가자의 수이다.

가령 제6회 ZOAC의 참가자 수는 총 2×6=12개의 기념품을 남김없이 동일하게 나눌 수 있는 2의 거듭제곱 수들 중 가장 큰 값이 되는 것이다. 12를 나누어 떨어지게 하는 2의 거듭제곱 수들은 2⁰, 2¹, 2²가 있으므로 이 수들 중 가장 큰 값인 2²가 제6회 ZOAC의 참가자 수가 된다. 원영이는 위 규칙들을 만족하도록 대회의 참가자 수를 정할 때 회차에 따른 ZOAC의 참가자의 수가 궁금하였다.

원영이의 궁금증을 풀어주기 위해 ZOAC의 회차 수 N이 주어졌을 때, 제1회 ZOAC부터 제N회 ZOAC까지 참가자 수의 합을 구하는 프로그램을 작성하시오.

첫 번째 줄에 자연수 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.

첫 번째 줄에 제1회 ZOAC부터 제N회 ZOAC까지의 참가자 수의 합을 출력한다.