1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

const int MAX_TIME = 11;

enum ParticleSequence{
	NotLimited, LimitedFromLeft, LimitedFromRight, LimitedFromBoth, EnumSize
};

ParticleSequence calculateLeftSequenceType(ParticleSequence parentType) {
	return (parentType == ParticleSequence::NotLimited || parentType == ParticleSequence::LimitedFromRight)
		? ParticleSequence::LimitedFromRight : ParticleSequence::LimitedFromBoth;
}

ParticleSequence calculateRightSequenceType(ParticleSequence parentType) {
	return (parentType == ParticleSequence::NotLimited || parentType == ParticleSequence::LimitedFromLeft)
		? ParticleSequence::LimitedFromLeft : ParticleSequence::LimitedFromBoth;
}

int calculateVanishTimeOfTwoSequences(ParticleSequence parentSequenceType, int leftSequenceVanishTime
	, int rightSequenceVanishTime) {
	switch (parentSequenceType) {
	case ParticleSequence::LimitedFromBoth:
		return (leftSequenceVanishTime == rightSequenceVanishTime) ? leftSequenceVanishTime + 1
			: std::max(leftSequenceVanishTime, rightSequenceVanishTime);
		break;
	case ParticleSequence::LimitedFromLeft:
		return (leftSequenceVanishTime >= rightSequenceVanishTime) ? leftSequenceVanishTime + 1
			: rightSequenceVanishTime;
		break;
	case ParticleSequence::LimitedFromRight:
		return (rightSequenceVanishTime >= leftSequenceVanishTime) ? rightSequenceVanishTime + 1
			: leftSequenceVanishTime;
		break;
	case ParticleSequence::NotLimited:
		return std::max(leftSequenceVanishTime, rightSequenceVanishTime) + 1;
	default:
		throw 0;
	}
}

std::vector<std::vector<std::vector<int>>> particleSequenceVanishTimes;
std::vector<std::vector<bool>> particleSequenceCalculated;

std::vector<std::vector<int>> binomialCoefficients;

std::vector<int>& calculateSequenceVanishTime(int lvl, int sequenceSize, ParticleSequence sequenceType, int moduloBase) {

	if (particleSequenceCalculated[sequenceType][sequenceSize]) {
		return particleSequenceVanishTimes[sequenceType][sequenceSize];
	}

	if (sequenceSize <= 1) {
		particleSequenceVanishTimes[sequenceType][sequenceSize][sequenceSize] = 1;
		particleSequenceCalculated[sequenceType][sequenceSize] = true;
		return particleSequenceVanishTimes[sequenceType][sequenceSize];
	}

	for (int i = 0; i < sequenceSize; ++i) {
		std::vector<int>& leftVanishTimeVec = calculateSequenceVanishTime(lvl+1,i
			, calculateLeftSequenceType(sequenceType), moduloBase);
		std::vector<int>& rightVanishTimeVec = calculateSequenceVanishTime(lvl+1,sequenceSize-i-1
			, calculateRightSequenceType(sequenceType), moduloBase);

		for (int leftVanishTime = 0;leftVanishTime < MAX_TIME;++leftVanishTime)
			for (int rightVanishTime = 0; rightVanishTime < MAX_TIME; ++rightVanishTime) {
				int totalCombinationsThisRun = (static_cast<long long int>(leftVanishTimeVec[leftVanishTime])
					* rightVanishTimeVec[rightVanishTime]) % moduloBase;
				totalCombinationsThisRun = static_cast<long long int>(totalCombinationsThisRun)*binomialCoefficients[sequenceSize-1][i]
					% moduloBase;

				int totalVanishTime = calculateVanishTimeOfTwoSequences(sequenceType, leftVanishTime, rightVanishTime);
				particleSequenceVanishTimes[sequenceType][sequenceSize][totalVanishTime] += totalCombinationsThisRun;
				particleSequenceVanishTimes[sequenceType][sequenceSize][totalVanishTime] %= moduloBase;
			}
	}

	particleSequenceCalculated[sequenceType][sequenceSize] = true;
	return particleSequenceVanishTimes[sequenceType][sequenceSize];

}

int main() {

	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	int numberOfParticles,requestedTime, resultModuloBase;
	std::cin >> numberOfParticles >> requestedTime >> resultModuloBase;

	binomialCoefficients.resize(numberOfParticles);
	binomialCoefficients[0] = std::vector<int>(1, 1);
	for (int n = 1; n < numberOfParticles; ++n) {
		binomialCoefficients[n].resize(n + 1);
		for (int k = 0; k <= n; ++k) {
			if (k > 0) binomialCoefficients[n][k] += binomialCoefficients[n - 1][k - 1];
			if (k < n) binomialCoefficients[n][k] += binomialCoefficients[n - 1][k];
			binomialCoefficients[n][k] %= resultModuloBase;
		}
	}

	particleSequenceVanishTimes.resize(ParticleSequence::EnumSize);
	particleSequenceCalculated.resize(ParticleSequence::EnumSize);
	
	for (int i = 0; i < ParticleSequence::EnumSize; ++i) {
		particleSequenceVanishTimes[i].resize(numberOfParticles+1);
		particleSequenceCalculated[i].resize(numberOfParticles+1);
		for (int j = 0; j < numberOfParticles+1; ++j) {
			particleSequenceVanishTimes[i][j].resize(MAX_TIME+1);
			std::fill(particleSequenceVanishTimes[i][j].begin(), particleSequenceVanishTimes[i][j].end(), 0);
			particleSequenceCalculated[i][j] = false;
		}
	}

	std::cout << ((requestedTime >= MAX_TIME)? 0 
		: calculateSequenceVanishTime(0, numberOfParticles, ParticleSequence::NotLimited, resultModuloBase)
		[requestedTime+1]) << "\n";

	return 0;

}