# [HAOI2018]苹果树

## 题目背景

HAOI2018 Round2 第一题

## 输入输出样例

### 输入样例 #1

3 610745795

### 输出样例 #1

24

### 输入样例 #2

305 1000000007

### 输出样例 #2

865018107

## 说明

![Explanation](https://cdn.luogu.com.cn/upload/pic/18067.png) 以上是所有 $N = 3$ 时可能的苹果树形态, 其中编号表示这个结点是第几天生 长出来的, 显然每种情况两两结点的距离均为 $4$ . ### 数据范围与约定 | 测试点编号 | $N$ | $P$ | | :--------: | :--: | :--: | | $1$ | $\le 10$ | $\le 10^9 + 7$ | | $2$ | $\le 10$ | $\le 10^9 + 7$ | | $3$ | $\le 500$ | $\le 10^9 + 7$ | | $4$ | $\le 500$ | $\le 10^9 + 7$ | | $5$ | $\le 500$ | $\le 10^9 + 7$ | | $6$ | $\le 2000$ | $= 10^9 + 7$ | | $7$ | $\le 2000$ | $= 10^9 + 7$ | | $8$ | $\le 2000$ | $\le 10^9 + 7$ | | $9$ | $\le 2000$ | $\le 10^9 + 7$ | | $10$ | $\le 2000$ | $\le 10^9 + 7$ |