Counting Good Functional Digraphs

We are given a directed graph with n white vertices and m black vertices. The white vertices are distinct and the black vertices are distinct. Each vertex has exactly one outgoing edge. For a white vertex the outgoing edge can point to any of the n+m vertices, while for a black vertex the outgoing edge must point to one of the white vertices only.

This defines a functional digraph (every vertex has out‐degree one) on n+m vertices – in other words a disjoint union of rooted trees attached to directed cycles.

A configuration (i.e. an assignment of an outgoing edge for every vertex) is said to be good if and only if the following conditions are satisfied:

• Every black vertex points to a white vertex.
• For every cycle in the graph, let w be the number of white vertices and b be the number of black vertices on that cycle. Then the product w × b must be even. (Note that a cycle containing only white vertices is always good, and a cycle cannot be composed solely of black vertices because of the first condition.)

The number of total configurations (without the cycle restriction) is (n+m)ⁿ × n^m because each of the n white vertices has n+m choices and each of the m black vertices has n choices. Your task is to count the number of good configurations modulo a given modulus P.

Note on cycles: In a functional digraph every vertex eventually lies in a unique cycle. In our count we “decompose” the function into the cycle part (which is a permutation on a certain subset of vertices obeying the extra conditions) and the tree part (each vertex not on a cycle points to some vertex on the cycle – note that for black vertices the pointer must be to a white vertex on the cycle).

Problem Summary: Given n, m and P, count the number of functions f from the set of n+m vertices to itself such that:

• If a vertex is black then f(vertex) is white.
• If C is any cycle in the functional digraph induced by f and if w (resp. b) is the number of white (resp. black) vertices in C then either C is all white or, if both colors appear, we require w × b to be even.

Output the number of good configurations modulo P.

inputFormat

The input consists of a single line containing three integers n, m and P — the number of white vertices, the number of black vertices, and the modulus.

You can assume that 1 ≤ n ≤ 10 and 0 ≤ m ≤ 10.

outputFormat

Output a single integer, the number of good configurations modulo P.

sample

1 0 1000000007

1