题目的大意：

• 首先，给你一个长度为n的序列A，A序列中每一个元素全都小于2^m，并且大于等于0。
• A序列要满足存在一个非空子序列的与运算(&)和为1；
• 输出这样的A序列有几个，最后对正整数q取模。（1 <= n , m <=5000 , 1 <= q <=10⁹)
• 输入只有一行n , m , q，输出包含一个整数。

题解：

　　要满足A序列的一个子序列 & 运算和为 1，则至少存在一个奇数。设A序列中存在k个整数，有n-k个偶数。

　　下图将每个数转换为2进制之后的 (m x k) 图 ，图中每一列都是一个数。

在这个图中每一行一共有2^k种，去除全是1的情况（因为在取子序列时所有数全是奇数，要保证最后&和的结果是1，则每一行至少有一个0）有2^k-1种，然后一共有m-1行，那么奇数总共有(2^k-1)^m-1种情况。

同理可得，偶数有2^(n-k)(m-1)种情况。

又因为实际情况中奇数和偶数都是随机的，则总共有C^k_n 2^(n-k)(m-1) · (2^k-1)^m-1种情况。最后再从1到n进行累加得 ∑ⁿ_k=1C^k_n 2^(n-k)(m-1) · (2^k-1)^m-1。

代码编写：

　　写代码的过程中主要有两个难点。一是求幂，因为k可以取到5000的，2⁵⁰⁰⁰已经超过了long long的数据范围，我的解决方法是快速幂。二是求组合数，这里我采用了杨辉三角求组合数。

　　先讲一下快速幂。举个例子，求3¹⁰，它可以变成9⁵ 。 这里5是奇数，我们将它变成 9 x 9⁴，继续降低它的幂，变成9 x 81²，最后变成 9 x (81²)¹。

　　在这个过程中，我们实际计算了(3*3)、(9*9)、(81*81)和 (9*81²)，我们需要计算10次，现在只需要计算4次，应用快速幂我们可以将O(n)的算法优化到O(logn)。

ll fast_POW(ll a ,ll b,ll c) //a是底数，b是指数，c是模
{
    ll ans=1;
    while(b)
    {
        if(b&1)//判断b是否为奇数
　　　　 {
            ans=(ans*a)%c;
        }
        a=(a*a)%c;
        b>>=1;//指数减小一倍
    }
    return ans;
}

　　然后再讲一下杨辉三角求组合数

　　首先Cⁿ_m=Cⁿ_m-1+C^n-1_m-1，取第m个数时可以分两种考虑取或者不取，如果取则从剩下的m-1个数中取n-1个数，如果不取则从剩下的m-1个数中取n个数。

　　那么就可以通过递推公式dp[ i ][ j ]=dp[ i-1 ][ j ] + dp[ i-1 ][ j-1]。 

typedef long long ll;
ll combination[5005][5005];

　　 int q=1e9;
    for(int i=0;i<=5001;i++)
    {
        combination[i][0]=1;
        combination[i][i]=1;
    }
    for(int i=1;i<=5001;i++)
    {
        for(int j=1;j<=i;j++)
        {
            combination[i][j]=(combination[i-1][j]%q+combination[i-1][j-1]%q)%q;//为了防止最后的值超出限制，要进行取模。
        }
    } 

　　完整代码：

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

ll combination[5005][5005];

ll fast_POW(ll a ,ll b,ll c)
{
    ll ans=1;
    while(b)
    {
        if(b&1){
            ans=(ans*a)%c;
        }
        a=(a*a)%c;
        b>>=1;
    }
    return ans;
}

inline ll comb(ll n, ll m)
{
    return combination[n][m];
 } 
void solve(ll n ,ll m , ll q)
{
    for(int i=0;i<=5001;i++)
    {
        combination[i][0]=1;
        combination[i][i]=1;
    }
    for(int i=1;i<=5001;i++)
    {
        for(int j=1;j<=i;j++)
        {
            combination[i][j]=(combination[i-1][j] % q +combination[i-1][j-1] %q)%q;//一定要注意取模，每一个可能超出模q的运算都要取模，不然会非常折磨。
        }
    } 
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ll ji=fast_POW(2, i ,q)-1;
        ans += comb(n , i)  * fast_POW(ji,m-1,q) %q * fast_POW(fast_POW(2,n-i,q),m-1,q);//一定要注意取模，每一次可能超出模q的运算都要取模，很折磨。
        ans=ans%q; 
    }
    cout << ans;
}


signed main()
{
    ll n,m,q;
    cin >> n >> m >> q;
    solve(n,m,q);
    return 0;
}