题号：NC24664
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
题目描述
As the final project of the Algorithm class, you and Ramen are going to design a new Random Number Generator called Hypercube Random Number Generator(HRNG), which is based on the idea of the hypercube.
What is a hypercube? The Wikipedia said:
In the problem, we define a hypercube using a pair)
, where 
is the dimensions of the hypercube and 
is the length of each dimension. For example, )
is a square which length is 100. Then we set one of its corners as the origin, so we get an -dimensional coordinate system. Each point inside the hypercube can be described as an -tuple like )
, and a integer point is that a point that 
. Especially, the origin's coordinate is )
.
The principle behind the HRNG is pretty easy. We can use a function)
to represent it. When we call it using a hypercube, it will randomly choose an integer point inside it with the same probability. Assume the point is )
, then the HRNG calculates the next value by %2B1)
. For example, if the hypercube is , we may obtain %3D47)
if the point it randomly choosed is )
.
In the report section, the teacher asked students to analysis their algorithm. Ramen has done the design work, so the review is your task. As an RNG, it should return each possible values with the same probability. In other words, the math expectation of HRNG should equal to the expected value of the discrete uniform distribution of
, i.e., 
. To measure your work, you need to compute the expected value of HRNG using given hypercube )
.
What is a hypercube? The Wikipedia said:
In geometry, a hypercube is an n-dimensional analogue of a square (n = 2) and a cube (n = 3, picture below). It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of space's dimensions, perpendicular to each other and of the same length.
In the problem, we define a hypercube using a pair
The principle behind the HRNG is pretty easy. We can use a function
In the report section, the teacher asked students to analysis their algorithm. Ramen has done the design work, so the review is your task. As an RNG, it should return each possible values with the same probability. In other words, the math expectation of HRNG should equal to the expected value of the discrete uniform distribution of
输入描述:
The input contains two integers n, p(1 <= n <= 1e18,1 <= p <= 100), represents the dimension of the hypercube and the length of each dimension.
输出描述:
Output the expected value of HRNG in one single line.
To avoid possible errors, if the answer is, you need to output
, i.e.,
, where
is the minimum number that suits
.
示例1