Hypercube High#2871
An -dimensional hypercube (or -cube) with side a > 0 is a figure in -dimensional Euclidean space, constructed as follows. Select any (N-1)-dimensional hyperplane in this space. Construct an (N-1)-cube in this hyperplane. From each vertex of this cube, draw a segment of length perpendicular to the chosen hyperplane in the same direction. The endpoints of these segments also lie in an (N-1)-dimensional hyperplane, parallel to the original, and form another (N-1)-cube. The convex hull of all these vertices (from both the original and the new (N-1)-cube) forms the -dimensional hypercube. By definition, a -cube is a point, which is its only vertex. It is easy to see that a -cube is a segment on a line; a -cube is a square on a plane; and a -cube is the usual cube in three-dimensional space. Hypercubes of higher dimensions are more difficult to visualize, but they can be formally constructed using this definition.
A -dimensional face (or -face) of an -dimensional hypercube is defined as the intersection of the -cube with a -dimensional hyperplane, not containing interior points of higher-dimensional faces. Each -cube has one -face that coincides with itself. It can be proved that -faces are -cubes. The -faces are the vertices of the -cube, -faces are its edges, and so on.
You must calculate the number of -dimensional faces of an -dimensional hypercube.
The input consists of a single line with three integers , , and (0 \leq k \leq N \leq 10^{18}, k \leq 2000, 1 \leq p \leq 10^{18}).
Output a single line with k+1 numbers: the remainder modulo of the number of -faces, -faces, ..., -faces of the -cube.
Esempio 1