/*
   dfs实际上是个模拟
*/
//len表示判断的是哪一位
ll dfs(ll len,int maxi,int k,int f){
    //dp[len][k][f]存储的是到长度为len为止，第k位为0和第k位为1的数是多少
    //maxi标志的是上一位模拟的数是不是等于num的这一位的数
    /*
       我们还是拿100来举例子，因为最高位我们得到的一定为1，所以传进来的时候maxi就是1
       那么我们第一位既可以模拟0也可是模拟1
       模拟0的时候，i != a[len]所以maxi = false，之后也都是false
       我们下一位就可以模拟00X跟01X，剩下的类似
       模拟1的时候，i == a[len]所以maxi = true
       我们就可以模拟1XX
       但是由于这时a[2] = 0所以只能模拟10X
       差不多就已经很清楚了
    */
    //dp[len][k][f]这里其实就是记忆化搜索，如果之前出现过，就直接返回结果就好。
    if(dp[len][k][f] != -1 && maxi == 0)
        return dp[len][k][f];
    //只有当第k位为1的情况这里才会加上1
    if(!len)
        return f;
    ll cnt = 0;
    int maxn = maxi ? a[len] : 1;
    //i这里代表着第len位的数字是多少
    //那么f||len == k && i就是判断这次模拟的数的第k位是否为1
    for(int i = 0;i <= maxn;i++){
        cnt += dfs(len - 1,maxi && i == a[len],k,f||len == k&&i);
    }
    //只有当maxi等于false的时候，我们模拟了下一位为0，1的全部情况,此时才更新dp的值
    //表示不受之前的数的限制，所求的只是[0,1 << (len) - 1]]满足条件的数
    return maxi ? cnt : dp[len][k][f] = cnt;
}

//二进制拆分数位,返回的结果是第k位为1的数总共有几个
ll div(ll num,int k){
    memset(a,0,sizeof(a));
    int index = 0;
    while(num){
        a[++index] = num % 2;
        num /= 2;
    }
    return dfs(index,1,k,0);
}