https://ac.nowcoder.com/acm/contest/67741/F
定义：n个两两区分的元素划分为，k个互不区分的非空子集的方案数。
https://oi-wiki.org/math/combinatorics/stirling/
使用容斥原理得到式子，然后n*快速幂logn的时间复杂度求。

对于例题，每个数大于零因此是“非空子集”的意义，每个数两两与运算为0表示一个位上只能有一个1，代表n个两两区分的元素。因此答案就是第二类斯特林数。

ps.不要忘了式子最后还要除一个m!

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
const ll mod = 1e9+7;
ll qmi(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res= res*a%mod;
        b>>=1;
        a= a*a%mod;
    }
    return res%mod;
}

ll fact[100010],ifact[100010];
void init(){
    fact[0] = ifact[0]=1;
    for(int i=1;i<=100000;i++){
        fact[i] = fact[i-1]*i%mod;
        ifact[i] = ifact[i-1]*qmi(i,mod-2)%mod;
    }
}

ll C(ll n,ll m){
    if(n<m) return 0;
    return fact[n]*ifact[m]%mod * ifact[n-m]%mod;
}


int main(){     
    //delete when submit!!!!!!
    freopen("in.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    ll n,m;
    cin>>n>>m;
    ll res=0;
    init();

    for(int k=0;k<=m;k++){
        if(k%2){
            res =  (res - C(m,k)*qmi(m-k,n)%mod + mod )%mod;
        }
        else{
            res =  (res + C(m,k)*qmi(m-k,n)%mod )%mod;
        }
    }
    cout<<res*ifact[m]%mod<<endl;
    return 0;
}