#3209. 花神的数论题

花神的数论题

题目背景

众所周知,花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC…… 当然也包括 CH 啦。

题目描述

话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。

花神的题目是这样的:

sum(i)sum(i) 表示 ii 的二进制表示中 11 的个数。给出一个正整数 nn ,花神要问你 Π1nsum(i)\Pi_{1}^{n}sum(i),也就是 sum(1)sum(n)sum(1)\sim sum(n) 的乘积。

输入格式

一个正整数 nn

输出格式

一个数,答案mod107+7\mod 10^7 + 7 的值。

3
2

样例说明

对于样例一,1×1×2=21 \times 1 \times 2 = 2

数据规模与约定

  • 对于 100%100\% 的数据,n1015n \leq 10^{15}

题目来源

原创 Memphis