Description

给定一个数n，将它分解成2^k的和的形式，求不同的分解数,K>=0。 例如当N=7时，有下面6种划分方法

1. 1+1+1+1+1+1+1
2. 1+1+1+1+1+2
3. 1+1+1+2+2
4. 1+1+1+4
5. 1+2+2+2
6. 1+2+4

Format

Input

一个数字N，N<=1e6

Output

输出结果的最后9位

Samples

7

6