6471: 最大乘积(product)

内存限制:256 MB 时间限制:2 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:0 通过:0

题目描述

黑板上有一个正整数 n。你可以做任意次如下的操作:选择一个黑板上的整数 x,把 x 擦掉,然后写上 floor(x/2) 和 ceil(x/2)。 
你要最大化黑板上所有数的乘积,输出这个乘积对 998244353 取模后的结果。 
提示:对于某个实数 k,floor(k) 表示不大于k的最大整数,ceil(k) 表示不小于k的最小整数。

输入格式

一行一个整数n。 

输出格式

一行一个整数,表示答案对 998244353 取模后的结果。 

输入样例 复制

3

输出样例 复制

3

数据范围与提示

样例输入2 
15 
样例输出2 
192 
样例1:不进行任何操作。 
样例2:擦掉 15,写上 7 和 8; 
擦掉 7,写上 3 和 4; 
擦掉 4,写上 2 和 2; 
擦掉 8,写上 4 和 4; 
黑板上的数有 3,2,2,4,4,乘积对 998244353 取模后的结果为 192。 
【数据范围约定】 
对于10%的数据,n≤5; 
对于20%的数据,n≤20; 
对于40%的数据,n≤50; 
对于60%的数据,n≤10^3; 
对于80%的数据,n≤10^6; 
对于90%的数据,n≤10^9; 
对于所有数据,1≤n≤10^18。