对于集合 $\{1,2,\dots,n\}$，求它的子集族中，有多少个满足：

1. 任意两个子集互不相同；
2. $1,2,\dots,n$ 都在其中至少出现了 $2$ 次。

答案对 $M$ 取模。

$2\le n\le 3000,10^8\le M\le10^9+9,M\in \text{prime}$