考虑容斥，我们可以求出用的建筑公司的集合至多是S的方案数(也就是最小生成树中的边只能用集合S内的建筑公司内的)，这个跑一下矩阵树定理就好啦(注意可以有重边，因为一条边被不同公司建是算不同的方案的)。

    然后再容斥加加减减算一算就好啦。。。

 

    (神TM我一开始忘了去掉一行一列答案一直是0 。。。。)

 

#include
     
      #define ll long longusing namespace std;const int ha=1e9+7;inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}inline void ADD(int &x,int y){ x+=y; if(x>=ha) x-=ha;}inline int ksm(int x,int y){	int an=1;	for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha;	return an;}int n,ci[25],ans,all;bool bt[200005];struct node{	int a[21][21];		inline void clear(){ memset(a,0,sizeof(a));}		node operator +(const node &b)const{		node r;		for(int i=1;i<=n;i++)		    for(int j=1;j<=n;j++) r.a[i][j]=add(a[i][j],b.a[i][j]);		return r;	}		inline int Get(){		int an=1;				for(int i=1,t,v;i