【题解】

　　题意其实就是把n个物品分成4个集合，其中三个集合不可以为空（只属于A、只属于B、AB的交），一个集合空或者非空都可以（不属于A也不属于B），问有多少种方案。

　　考虑容斥，4个集合都不为空的方案数有4^n-4*3^n+6*2^n-4，3个集合不为空的方案数有3^n-3*2^n+3. 相加就是总的方案数。

　　不过题目中认为(A,B)、(B,A)是同一种方案，所以答案要除以二。

1 #include
     
       2 #include
      
        3 #include
       
         4 #define LL long long 5 #define N 200010 6 using namespace std; 7 const LL Mod=1e8+7; 8 LL n; 9 inline LL read(){10     LL k=0,f=1; char c=getchar();11     while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();12     while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();13     return k*f;14 }15 inline LL pow(int x,LL y){16     LL t=x,ans=1;17     for(;y;y>>=1,t=(t*t)%Mod) if(y&1) ans*=t,ans%=Mod;18     return ans;19 }20 int main(){21     n=read();22     printf("%lld\n",((1ll*pow(4,n)-4*pow(3,n)%Mod+6*pow(2,n)%Mod-4+pow(3,n)-3*pow(2,n)%Mod+3+Mod)%Mod*(Mod+1)/2)%Mod);23     return 0;24 }