地精喜欢居住在连绵不绝的山脉中，一段长度为N的山脉可分为N段，每段有一个独一无二的高度Hi，Hi是1到N之间的正整数。
对于每一段山脉，若它比与它相邻的两段（处于边缘的山脉只与一段山脉相邻）山脉都高，则称这段山脉为一段山峰；若它比相邻的山脉都矮，则称它为山谷。
地精对适宜居住的山脉有两个要求，地精喜欢饮酒，而且偏好把酒馆建在山谷中；地精还十分警觉，他们在每座山峰顶部都建立瞭望台，以防御外敌入侵；地精们希望，一座适宜居住的山脉，其中的每一段都应当能建设酒馆或瞭望台。
地精们会告诉你一座山脉的长度N，他们想知道长度为N的宜居山脉一共会有多少种。两座山脉A与B不同，当且仅当存在至少一i，使得Ai ≠ Bi。由于这个方案数可能很大，最终答案应对P取模。