문제
길이 $N$의 정수열 $A$의 모든 원소를 Bitwise XOR한 값이 $X$일 때 $A$를 신기한 수열이라고 한다. $(0 \leq A_i < 2^M)$
가능한 모든 길이 $N$의 신기한 수열 중에서 균등한 확률로 수열 $A$를 골랐을 때 $\sum_{i=1}^{N}{ A_i }$의 기댓값을 구해보자.
출력
$\sum_{i=1}^{N}{A_i}$의 기댓값을 소수 10ドル^9+7(=1,000円,000円,007円)$로 나눈 나머지를 출력한다.
서로소인 두 양의 정수 $a, b$에 대해 유리수 $\frac{b}{a}$를 10ドル^9+7$으로 나눈 나머지란, $a \times x \equiv b \pmod{10^9+7}$이며 10ドル^9+7$ 미만인 음이 아닌 정수 $x$를 의미한다.
가능한 모든 입력에 대해 그러한 $x$가 존재하며 유일함을 증명할 수 있다.
W3sicHJvYmxlbV9pZCI6IjI5NzYzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMmUwXHVhZTMwXHVkNTVjIFx1YzIxOFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVhZTM4XHVjNzc0ICROJFx1Yzc1OCBcdWM4MTVcdWMyMThcdWM1ZjQgJEEkXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM2ZDBcdWMxOGNcdWI5N2MgQml0d2lzZSBYT1JcdWQ1NWMgXHVhYzEyXHVjNzc0ICRYJFx1Yzc3YyBcdWI1NGMgJEEkXHViOTdjIDxzdHJvbmc+XHVjMmUwXHVhZTMwXHVkNTVjIFx1YzIxOFx1YzVmNDxcL3N0cm9uZz5cdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiAkKDAgXFxsZXEgQV9pICZsdDsgMl5NKSQ8XC9wPlxyXG5cclxuPHA+XHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWFlMzhcdWM3NzQgJE4kXHVjNzU4IFx1YzJlMFx1YWUzMFx1ZDU1YyBcdWMyMThcdWM1ZjQgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWRlMFx1YjRmMVx1ZDU1YyBcdWQ2NTVcdWI5NjBcdWI4NWMgXHVjMjE4XHVjNWY0ICRBJFx1Yjk3YyBcdWFjZThcdWI3OTBcdWM3NDQgXHViNTRjICRcXHN1bV97aT0xfV57Tn17IEFfaSB9JFx1Yzc1OCBcdWFlMzBcdWIzMTNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCAkTiQsICRNJFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxIFxcbGVxIE4gXFxsZXEgMTBeezE4fTskICQxIFxcbGVxIE0gXFxsZXEgMjAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCAkWCRcdWFjMDAgXHViZDgwXHVkNjM4IFx1YzVjNlx1YjI5NCAkTSRcdWM3OTBcdWI5YWMgXHVjNzc0XHVjOWM0XHVjMjE4IFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiRcXHN1bV97aT0xfV57Tn17QV9pfSRcdWM3NTggXHVhZTMwXHViMzEzXHVhYzEyXHVjNzQ0IFx1YzE4Y1x1YzIxOCAkMTBeOSs3KD0xXFwsMDAwXFwsMDAwXFwsMDA3KSRcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzExY1x1Yjg1Y1x1YzE4Y1x1Yzc3OCBcdWI0NTAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCAkYSwgYiRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YzcyMFx1YjlhY1x1YzIxOCAkXFxmcmFje2J9e2F9JFx1Yjk3YyAkMTBeOSs3JFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViNzgwLCAkYSBcXHRpbWVzIHggXFxlcXVpdiBiIFxccG1vZHsxMF45Kzd9JFx1Yzc3NFx1YmE3MCAkMTBeOSs3JCBcdWJiZjhcdWI5Y2NcdWM3NzggXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMTggJHgkXHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWM3ODVcdWI4MjVcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YWRmOFx1YjdlY1x1ZDU1YyAkeCRcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHViYTcwIFx1YzcyMFx1Yzc3Y1x1ZDU2OFx1Yzc0NCBcdWM5OWRcdWJhODVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyOTc2MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZhc2NpbmF0aW5nIFNlcXVlbmNlIiwiZGVzY3JpcHRpb24iOiI8cD5BIHNlcXVlbmNlICRBJCBvZiBsZW5ndGggJE4kIGlzIHNhaWQgdG8gYmUgPHN0cm9uZz5mYXNjaW5hdGluZzxcL3N0cm9uZz4gaWYgdGhlIGJpdHdpc2UgWE9SIG9mIGFsbCBpdHMgZWxlbWVudHMgeWllbGRzICRYJC4gJCgwIFxcbGVxIEFfaSAmbHQ7IDJeTSkkPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZXNlIGNvbnN0cmFpbnRzLCZuYnNwO2NvbXB1dGUgdGhlIGV4cGVjdGVkIHZhbHVlIG9mIHRoZSBzdW0gb2YgYWxsIGVsZW1lbnRzIGluICRBJCwgZ2l2ZW4gdGhhdCAkQSQgaXMgY2hvc2VuIHVuaWZvcm1seSBhdCByYW5kb20gYW1vbmcgYWxsIGZhc2NpbmF0aW5nIHNlcXVlbmNlcyBvZiBsZW5ndGggJE4kLjxcL3A+XHJcbiIsImlucHV0IjoiXHJcbjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycywgJE4kIGFuZCAkTSQsIHNlcGFyYXRlZCBieSBhIHNwYWNlLiAkKDEgXFxsZXEgTiBcXGxlcSAxMF57MTh9OyQgJDEgXFxsZXEgTSBcXGxlcSAyMDBcXCwwMDApJDxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgJFgkLCBhbiB1bnNpZ25lZCBiaW5hcnkgbnVtYmVyIG9mICRNJCBkaWdpdHMuPFwvcD5cclxuXHJcbiIsIm91dHB1dCI6IlxyXG48cD5PdXRwdXQgdGhlIHJlbWFpbmRlciB3aGVuIGRpdmlkaW5nIHRoZSBleHBlY3RlZCB2YWx1ZSBvZiAkXFxzdW1fe2k9MX1ee059e0FfaX0kIGJ5ICQxMF45KzcoPTFcXCwwMDBcXCwwMDBcXCwwMDcpJCwgd2hpY2ggaXMgYSBwcmltZS48XC9wPlxyXG5cclxuPHA+Rm9yIGFueSB0d28gY29wcmltZSBwb3NpdGl2ZSBpbnRlZ2VycyAkYSwgYiQsIHRoZSByZW1haW5kZXIgb2YgdGhlIHJhdGlvbmFsIG51bWJlciAkXFxmcmFje2J9e2F9JCZuYnNwO2RpdmlkZWQgYnkgJDEwXjkrNyQgaXMgdGhlIG5vbi1uZWdhdGl2ZSBpbnRlZ2VyICR4JCBzdWNoIHRoYXQgJGEgXFx0aW1lcyB4IFxcZXF1aXYgYiBcXHBtb2R7MTBeOSs3fSQgYW5kICR4Jmx0OzEwXjkrNyQuPFwvcD5cclxuXHJcbjxwPkZvciBldmVyeSBwb3NzaWJsZSBpbnB1dCwgaXQgY2FuIGJlIHByb3ZlbiB0aGF0IHN1Y2ggYW4gJHgkIGV4aXN0cyBhbmQgaXMgdW5pcXVlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=