Background

小明是一个爱装逼的好孩纸，今天他继续他伟大光荣的装逼事业。

Description

今天小明决定做一个二人。他想知道任何一个整数n拆成2的幂次之和，有几种拆法（数字相同顺序不同算同一种）。例如n=5，共有4种方法：\(5=4+1=2+2+1=2+1+1+1=1+1+1+1+1\)。注意如果n本身是2的幂次，则n=n也算一种拆法。~~（猜猜小明今天会不会在二海中迷茫而真的变成一个二人呢？）~~

Format

Input

一个正整数n

Output

拆法总数对100000007取模

Sample 1

Input

5

Output

4

Limitation

1s, 1024KiB for each test case.

Hint

n≤1e9（注意数据范围哦）