import std.bigint,std.stdio,std.string;enum M=10^^9+7,S=M/85;long y,z,e,j;void i(){for(y=1,e=M-2;e;e/=2,z=z*z%M)y=e%2?y*z%M:y;}void f(long n){if(n>M-n)f(M-1-n),i,z=n%2?y:M-y;else{if(n%SJU(TG:F*NDA_<