#include <stdio.h>
int foo(int n)
{
if (n < 30) return 1 << n;
int re = (1 << 30) % 1000000007;
for(int i=31; n>i; i++)
{
re <<= 1;
if (re > 1000000007) re -= 1000000007;
}
return re;
}
int main()
{
int n;
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CgppbnQgZm9vKGludCBuKQp7CiAgICBpZiAobiA8IDMwKSByZXR1cm4gMSA8PCBuOwogICAgaW50IHJlID0gKDEgPDwgMzApICUgMTAwMDAwMDAwNzsKICAgIGZvcihpbnQgaT0zMTsgbj5pOyBpKyspCiAgICB7CiAgICAgICAgcmUgPDw9IDE7CiAgICAgICAgaWYgKHJlID4gMTAwMDAwMDAwNykgcmUgLT0gMTAwMDAwMDAwNzsKICAgIH0KICAgIHJldHVybiByZTsKfQoKCmludCBtYWluKCkKewoJaW50IG47CglzY2FuZigiJWQiLCZuKTsKCXByaW50ZigiJWQiLGZvbyhuKSk7CglyZXR1cm4gMDsKfQ==