Problem Statement

Given a tree T, we can produce a new tree T' as follows: T' will contain the entire tree T.
Additionally, for each vertex x in T, add a new vertex to T' and attach it to x. We will call this
procedure growing the tree.

You are given ints N, D, and P. Start with a tree that consists of a single vertex. Grow this tree N
times to produce a tree with 2^N vertices. In that tree, count all simple paths of length D, and
return that count modulo the prime P.

The length of a simple path is the number of edges it contains. Two simple paths are considered
different if they contain a different set of edges. In other words, the direction in which the path
is traversed does not matter.


Method signature: int sumup(int N, int D, int P)
Time limit (s): 2.000
Memory limit (MB): 256


Constraints

- N will be between 1 and 1,000,000,000, inclusive.
- D will be between 1 and 500, inclusive.
- P will be between 503 and 1,000,000,009, inclusive.
- P will be a prime.


Examples

0)

3
3
1000000007
Returns: 8

The eight paths are shown in orange in the figure below. You may also note that the size of the
nodes corresponds to their "generation": the largest node is the original one, the smallest nodes
are the ones that were added when the tree grew for the last time.

(A figure with the paths is here. The tree looks as follows (the numbers are generations):
0
|
+----+----+
|    |    |
1    2    3
|    |
+-+  |
| |  |
2 3  3
|
|
|
3

)


1)

1
10
503
Returns: 0

There is no path of length 10 because the tree is too small.


2)

10
1
503
Returns: 17


3)

10
5
1000000009
Returns: 21352


4)

987654321
500
1000000009
Returns: 420937613


This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.