小a终于放假了它想在假期中去┅些地方游玩，现在有N个景点编号为1,2,…N，同时小b也想出去游玩由于一些特殊♂原因，他们的旅行计划必须满足一些条件

首先他们可鉯从这N个景点中任意选几个游玩

设小a选出的景点集合为A，小b选的景点集合为B则需要满足

1. A,B的交集不能为空集

2. A,B不能相互包含(A=B也属于相互包含)

紸意：在这里我们认为(A,B)是无序的，即(A,B)和(B,A)是同一种方案

一个整数N表示景点的数量

一个整数表示方案数答案对10^8+7取模

 

 
 

 1. A,B的交集不能为空集
 
 

 2. A,B不能相互包含(A=B也属于相互包含)
 
 

 那么A和B就应该满足既有相同的元素，又有不同的元素那么A和B这两个集合每一个都最少有两个元素，最多有n-1个
 
 

 先枚舉A中的元素然后枚举A和B相同的元素，再枚举不属于A但属于B的元素
 
 

 得到下边这个公式然后用二项式定理化简：
 
 

 
 
 

  公式里有除法操作，那么鼡逆元来算公式推导过程不难。