Alice and Bobo are playing a game on a graph with n vertices numbered with 0,1,…,. The vertex numbered with i is associated with weight 2i2^i2i. The game is played as follows. Firstly, Alice chooses a subset of the n2frac{n}{2}2n edges. Subsequently Bobo chooses a subset of the n vertices to *cover* the edges chosen by Alice. An edge is *covered* if one of its two ends is chosen by Bobo. As Bobo is smart, he will choose a subset of vertices whose sum of weights, denoted as S, is minimum. Alice would like to know the number of subsets of edges where Bobo will choose a subset whose sum of weights is exactly k , modulo .
Alice and Bobo are playing a game on a graph with n vertices numbered with 0,1,…,(n−1)0, 1, dots, (n - 1)0,1,…,(n−1). The vertex numbered with i is associated with weight 2i2^i2i. The game is played as follows. Firstly, Alice chooses a (possibly empty) subset of the n(n−1)2frac{n(n - 1)}{2}2n(n−1) edges. Subsequently Bobo chooses a (possibly empty) subset of the n vertices to *cover* the edges chosen by Alice. An edge is *covered* if one of its two ends is chosen by Bobo. As Bobo is smart, he will choose a subset of vertices whose sum of weights, denoted as S, is minimum. Alice would like to know the number of subsets of edges where Bobo will choose a subset whose sum of weights is exactly k (i.e. S = k), modulo (109+7)(10^9+7)(109+7).