#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<vector>
#include<set>
using namespace std;
const int mod=1e9+7;
typedef long long LL;
int power(int a,int n)
{
if(n==0)
return 1;
int ret=power(a,n/2);
ret=1LL*ret*ret%mod;
if(n%2)
ret=1LL*ret*a%mod;
return ret;
}
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=a; i<=b; ++i)
#define PER(i,a,b) for(int i=a; i>=b; --i)
#define MP make_pair
#define PB push_back
#define fi first
#define se second
typedef pair<int,int> pii;
int ex[1101],fac[1101],f[2101],inv[1101];
const double PI = acos(-1.0);
const int Bin = 11;
const int P=1e9+7;
const int maxn = (1<<Bin);
const int md=1e9+7;
const int mmd =(1<<15);
vector<int> vec[12];
struct Comp {
double re, im;
Comp(): re(0), im(0) {}
Comp(const double _re, const double _im) { re = _re; im = _im; }
Comp operator+(const Comp &a) { return Comp(re+a.re, im+a.im); }
Comp operator-(const Comp &a) { return Comp(re-a.re, im-a.im); }
Comp operator*(const Comp &a) { return Comp(re*a.re-im*a.im, re*a.im+im*a.re); }
Comp operator*(const double &a) { return Comp(re*a, im*a); }
Comp operator/(const double &a) { return Comp(re/a, im/a); }
void operator*=(const Comp &a) { (*this) = (*this) * a; }
void operator+=(const Comp &a) { re += a.re; im += a.im; }
void operator*=(const double &a) { re*=a; im*=a; }
void operator/=(const double &a) { re/=a; im/=a; }
Comp conj() { return Comp(re, -im); }
};
vector<Comp> ww[Bin + 2];
void Init() {
for(int i = 1, l = 2; l <= maxn; ++i, l <<= 1) {
for(int k = 0; k < l/2; ++k)
ww[i].push_back(Comp(cos(2*PI*k/l),sin(2*PI*k/l)));
}
}
void FFT(Comp *a, int len, int type) {
int i, j, k, l, tt;
for(i = 1, j = len>>1; i < len-1; ++i) {
if(i < j) swap(a[i], a[j]);
k = len>>1;
while(j >= k) j -= k, k >>= 1;
j += k;
}
Comp var, u, v;
for(l = 2, tt = 1; l <= len; l <<= 1, ++tt) {
for(k = 0; k < len; k += l) {
for(i = k; i < k+l/2; ++i) {
var = ww[tt][i-k];
if(type == -1) var.im = -var.im;
u = a[i], v = var * a[i+l/2];
a[i] = u+v, a[i+l/2] = u-v;
}
}
}
if(type == -1) for(i = 0; i < len; ++i) a[i] /= len;
}
Comp A[maxn + 5], B[maxn + 5], C[maxn + 5], DD[maxn + 5];
int aa[maxn*2],bb[maxn*2],cc[maxn*2],dd[maxn*2];
void Conv(int *a, int *b, int *c, int len) {
for(int i = 0; i < len; ++i) {
A[i] = Comp(a[i]>>15, b[i]>>15);
B[i] = Comp(a[i]&(mmd-1), b[i]&(mmd-1));
}
FFT(A, len, 1); FFT(B, len, 1);
for(int i = 0; i < len; ++i) {
int j = (len-i) & (len-1);
C[i] = (A[i]*A[i] - (A[j]*A[j]).conj()) * Comp(0, -0.25)+(A[i]*B[i] - (A[j]*B[j]).conj()) * Comp(0.5, 0);
DD[i] = (B[i]*B[i] - (B[j]*B[j]).conj()) * Comp(0, -0.25);
}
FFT(C, len, -1); FFT(DD, len, -1);
for(int i = 0; i < len; ++i) {
c[i] = (((LL(C[i].re+0.5) %mod)<<30)%mod + ((LL(C[i].im+0.5)%mod ) <<15)%mod+ LL(DD[i].re+0.5))%mod ;
}
}
inline int read(){
int f=1,x=0;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return f*x;
}
inline int qpow(int x,int p){int ans=1;
for(;p;p>>=1,x=1ll*x*x%P)if(p&1)ans=1ll*ans*x%P;
return ans;
}
int temp[maxn],a[maxn],b[maxn],c[maxn],d[maxn],tmp[maxn];
inline void GetInv(int *a,int *b,int n){
if (n==1) return void(b[0]=qpow(a[0],P-2));
GetInv(a,b,n>>1);
for (int i=0;i<n;++i)tmp[i]=a[i],tmp[n+i]=0;
int k;for (k=1;k<=n;k<<=1);
for (int i=n;i<k;++i)b[i]=0;
Conv(tmp,b,tmp,k);
for(int i=n;i<k;i++)
tmp[i]=0;
Conv(tmp,b,tmp,k);
for (int i=0;i<n;++i)b[i]=(2*b[i]%mod-tmp[i]+mod)%mod,b[n+i]=0;
}
inline void Getln(int *a,int *b,int *c,int n){
for (int i=0;i<n;++i)b[i]=1ll*(i+1)*a[i+1]%P;
GetInv(a,c,n);
for (int i=0;i<n;++i)tmp[i]=c[i],tmp[n+i]=0;
int k;for (k=1;k<=n;k<<=1);
Conv(tmp,b,tmp,k);
for (int i=1;i<=n;++i)b[i]=1ll*tmp[i-1]*qpow(i,P-2)%P,b[i+n]=0;b[0]=0;
}
inline void Getexp(int *a,int *b,int *c,int *d,int n){
if (n==1)return void(b[0]=1);
Getexp(a,b,c,d,n>>1);
Getln(b,c,d,n);
for (int i=0;i<n;++i)tmp[i]=(a[i]-c[i]+P)%P,tmp[n+i]=0;++tmp[0];
int k;for (k=1;k<=n;k<<=1);
Conv(tmp,b,tmp,k);
for (int i=0;i<n;++i)b[i]=tmp[i],b[i+n]=0;
}
void got(int n,int deep)
{
int i;
if(n==1)
{
vec[deep].push_back(1);
vec[deep].push_back(1);
return;
}
got(n>>1,deep+1);
vec[deep].resize(n+1);
int d=n>>1;
for(i=0;i<=n;i++)
{
if(i==0)
ex[i]=1;
else
ex[i]=1LL*ex[i-1]*d%mod;
}
int len=1;
while(len<=d+d)
len<<=1;
for(i=0;i<len;i++)
{
if(i<=(n>>1))
{
aa[i]=1LL*ex[(n>>1)-i]*inv[(n>>1)-i]%mod;
bb[i]=1LL*fac[i]*vec[deep+1][i]%mod;
}
else
bb[i]=aa[i]=0;
}
Conv(aa,bb,cc,len);
for(i=0;i<=d;i++)
cc[i]=1LL*cc[i+(n>>1)]*inv[i]%mod;
for(i=d+1;i<len;i++)
cc[i]=0;
for(i=0;i<len;i++)
{
if(i<=(n>>1))
aa[i]=vec[deep+1][i];
else
aa[i]=0;
}
Conv(aa,cc,bb,len);
if(n&1)
{
for(i=0;i<=n;i++)
{
vec[deep][i]=1LL*bb[i]*n%mod;
vec[deep][i]=(vec[deep][i]+bb[i-1])%mod;
}
}
else
{
for(i=0;i<=n;i++)
vec[deep][i]=bb[i];
}
}
int CC(int n,int m)
{
return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
long long S,T;
int n,m;
int main()
{
Init();
scanf("%lld%lld%d%d",&S,&T,&n,&m);
int i,j,s,p,q;
for(i=0;i<=m-n+1;i++)
{
if(i==0)
fac[i]=1;
else
fac[i]=1LL*fac[i-1]*i%mod;
}
inv[m-n+1]=power(fac[m-n+1],mod-2);
for(i=m-n;i>=0;i--)
inv[i]=1LL*inv[i+1]*(i+1)%mod;
int len=1;
while(len<=m-n)
len<<=1;
got(m-n,0);
S=(S-(m-n)+mod)%mod;
T%=mod;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(i=1;i<=m-n;i++)
b[i]=inv[i+1];
b[0]=1;
GetInv(b,a,len);
for(i=0;i<=m-n+1;i++)
{
if(i==0)
ex[i]=1;
else
ex[i]=1LL*ex[i-1]*(T+1)%mod;
}
for(i=0;i<=m-n;i++)
{
b[i]=1LL*(ex[i+1]-1)*inv[i+1]%mod;
if(b[i]<0)
b[i]+=mod;
}
for(i=m-n+1;i<len<<1;i++)
a[i]=b[i]=0;
Conv(a,b,f,len<<1);
for(i=0;i<=m-n;i++)
{
f[i]=1LL*f[i]*fac[i]%mod;
if(f[i]<0)
f[i]+=mod;
}
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
int x,y;
for(i=0;i<=m-n;i++)
{
a[i]=1LL*f[i]*inv[i]%mod;
if(i%2)
a[i]=(mod-a[i])%mod;
if(i==0)
{
x=power(a[i],mod-2);
y=power(a[i],n);
}
a[i]=1LL*a[i]*x%mod;
}
Getln(a,b,c,len);
for(i=0;i<=m-n;i++)
b[i]=1LL*b[i]*n%mod;
for(i=m-n+1;i<len;i++)
b[i]=0;
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
Getexp(b,a,c,d,len);
for(i=0;i<=m-n;i++)
a[i]=1LL*a[i]*y%mod;
int awp=1;
for(i=0;i<=m-n;i++)
{
b[i]=1LL*awp*inv[i]%mod;
awp=1LL*awp*S%mod;
}
for(i=m-n+1;i<len<<1;i++)
a[i]=b[i]=0;
Conv(a,b,c,len<<1);
int ans=0;
for(i=0;i<=m-n;i++)
ans=(ans+1LL*c[i]*vec[0][i]%mod*fac[i])%mod;
ans=1LL*ans*inv[m-n]%mod;
printf("%d\n",ans);
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGNzdGRsaWI+CiNpbmNsdWRlPGNzdHJpbmc+CiNpbmNsdWRlPGFsZ29yaXRobT4KI2luY2x1ZGU8Y21hdGg+CiNpbmNsdWRlPHN0ZGlvLmg+CiNpbmNsdWRlPHZlY3Rvcj4KI2luY2x1ZGU8c2V0Pgp1c2luZyBuYW1lc3BhY2Ugc3RkOwpjb25zdCBpbnQgbW9kPTFlOSs3OyAKdHlwZWRlZiBsb25nIGxvbmcgTEw7IAppbnQgcG93ZXIoaW50IGEsaW50IG4pCnsKCWlmKG49PTApCgkgICByZXR1cm4gMTsKCWludCByZXQ9cG93ZXIoYSxuLzIpOwoJcmV0PTFMTCpyZXQqcmV0JW1vZDsKCWlmKG4lMikKCSAgIHJldD0xTEwqcmV0KmElbW9kOwoJcmV0dXJuIHJldDsKfQoKI2RlZmluZSBpbmYgMHgzZjNmM2YzZgojZGVmaW5lIG1lbShhLGIpIG1lbXNldChhLGIsc2l6ZW9mKGEpKQojZGVmaW5lIFJFUChpLGEsYikgZm9yKGludCBpPWE7IGk8PWI7ICsraSkKI2RlZmluZSBQRVIoaSxhLGIpIGZvcihpbnQgaT1hOyBpPj1iOyAtLWkpCiNkZWZpbmUgTVAgbWFrZV9wYWlyCiNkZWZpbmUgUEIgcHVzaF9iYWNrCiNkZWZpbmUgZmkgZmlyc3QKI2RlZmluZSBzZSBzZWNvbmQKdHlwZWRlZiBwYWlyPGludCxpbnQ+IHBpaTsKaW50IGV4WzExMDFdLGZhY1sxMTAxXSxmWzIxMDFdLGludlsxMTAxXTsKY29uc3QgZG91YmxlIFBJID0gYWNvcygtMS4wKTsKY29uc3QgaW50IEJpbiA9IDExOwpjb25zdCBpbnQgUD0xZTkrNzsKY29uc3QgaW50IG1heG4gPSAoMTw8QmluKTsKY29uc3QgaW50IG1kPTFlOSs3Owpjb25zdCBpbnQgbW1kID0oMTw8MTUpOwp2ZWN0b3I8aW50PiB2ZWNbMTJdOwpzdHJ1Y3QgQ29tcCB7CiAgICBkb3VibGUgcmUsIGltOwogICAgQ29tcCgpOiByZSgwKSwgaW0oMCkge30KICAgIENvbXAoY29uc3QgZG91YmxlIF9yZSwgY29uc3QgZG91YmxlIF9pbSkgeyByZSA9IF9yZTsgaW0gPSBfaW07IH0KICAgIENvbXAgb3BlcmF0b3IrKGNvbnN0IENvbXAgJmEpIHsgcmV0dXJuIENvbXAocmUrYS5yZSwgaW0rYS5pbSk7IH0KICAgIENvbXAgb3BlcmF0b3ItKGNvbnN0IENvbXAgJmEpIHsgcmV0dXJuIENvbXAocmUtYS5yZSwgaW0tYS5pbSk7IH0KICAgIENvbXAgb3BlcmF0b3IqKGNvbnN0IENvbXAgJmEpIHsgcmV0dXJuIENvbXAocmUqYS5yZS1pbSphLmltLCByZSphLmltK2ltKmEucmUpOyB9CiAgICBDb21wIG9wZXJhdG9yKihjb25zdCBkb3VibGUgJmEpIHsgcmV0dXJuIENvbXAocmUqYSwgaW0qYSk7IH0KICAgIENvbXAgb3BlcmF0b3IvKGNvbnN0IGRvdWJsZSAmYSkgeyByZXR1cm4gQ29tcChyZS9hLCBpbS9hKTsgfQogICAgdm9pZCBvcGVyYXRvcio9KGNvbnN0IENvbXAgJmEpIHsgKCp0aGlzKSA9ICgqdGhpcykgKiBhOyB9CiAgICB2b2lkIG9wZXJhdG9yKz0oY29uc3QgQ29tcCAmYSkgeyByZSArPSBhLnJlOyBpbSArPSBhLmltOyB9CiAgICB2b2lkIG9wZXJhdG9yKj0oY29uc3QgZG91YmxlICZhKSB7IHJlKj1hOyBpbSo9YTsgfQogICAgdm9pZCBvcGVyYXRvci89KGNvbnN0IGRvdWJsZSAmYSkgeyByZS89YTsgaW0vPWE7IH0KICAgIENvbXAgY29uaigpIHsgcmV0dXJuIENvbXAocmUsIC1pbSk7IH0KfTsKCnZlY3RvcjxDb21wPiB3d1tCaW4gKyAyXTsKdm9pZCBJbml0KCkgewogICAgZm9yKGludCBpID0gMSwgbCA9IDI7IGwgPD0gbWF4bjsgKytpLCBsIDw8PSAxKSB7CiAgICAgICBmb3IoaW50IGsgPSAwOyBrIDwgbC8yOyArK2spCgkgICAgCXd3W2ldLnB1c2hfYmFjayhDb21wKGNvcygyKlBJKmsvbCksc2luKDIqUEkqay9sKSkpOwogICAgfQp9Cgp2b2lkIEZGVChDb21wICphLCBpbnQgbGVuLCBpbnQgdHlwZSkgewogICAgaW50IGksIGosIGssIGwsIHR0OwogICAgZm9yKGkgPSAxLCBqID0gbGVuPj4xOyBpIDwgbGVuLTE7ICsraSkgewogICAgICAgIGlmKGkgPCBqKSBzd2FwKGFbaV0sIGFbal0pOwogICAgICAgIGsgPSBsZW4+PjE7CiAgICAgICAgd2hpbGUoaiA+PSBrKSBqIC09IGssIGsgPj49IDE7CiAgICAgICAgaiArPSBrOwogICAgfQogICAgQ29tcCB2YXIsIHUsIHY7CiAgICBmb3IobCA9IDIsIHR0ID0gMTsgbCA8PSBsZW47IGwgPDw9IDEsICsrdHQpIHsKICAgICAgICBmb3IoayA9IDA7IGsgPCBsZW47IGsgKz0gbCkgewogICAgICAgICAgICBmb3IoaSA9IGs7IGkgPCBrK2wvMjsgKytpKSB7CiAgICAgICAgICAgICAgICB2YXIgPSB3d1t0dF1baS1rXTsKICAgICAgICAgICAgICAgIGlmKHR5cGUgPT0gLTEpIHZhci5pbSA9IC12YXIuaW07CiAgICAgICAgICAgICAgICB1ID0gYVtpXSwgdiA9IHZhciAqIGFbaStsLzJdOwogICAgICAgICAgICAgICAgYVtpXSA9IHUrdiwgYVtpK2wvMl0gPSB1LXY7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBpZih0eXBlID09IC0xKSBmb3IoaSA9IDA7IGkgPCBsZW47ICsraSkgYVtpXSAvPSBsZW47Cn0KQ29tcCBBW21heG4gKyA1XSwgQlttYXhuICsgNV0sIENbbWF4biArIDVdLCBERFttYXhuICsgNV07CmludCBhYVttYXhuKjJdLGJiW21heG4qMl0sY2NbbWF4bioyXSxkZFttYXhuKjJdOwp2b2lkIENvbnYoaW50ICphLCBpbnQgKmIsIGludCAqYywgaW50IGxlbikgewogICAgZm9yKGludCBpID0gMDsgaSA8IGxlbjsgKytpKSB7CiAgICAgICAgQVtpXSA9IENvbXAoYVtpXT4+MTUsIGJbaV0+PjE1KTsKICAgICAgICBCW2ldID0gQ29tcChhW2ldJihtbWQtMSksIGJbaV0mKG1tZC0xKSk7CiAgICB9CiAgICBGRlQoQSwgbGVuLCAxKTsgRkZUKEIsIGxlbiwgMSk7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbGVuOyArK2kpIHsKICAgICAgICBpbnQgaiA9IChsZW4taSkgJiAobGVuLTEpOwogICAgICAgIENbaV0gPSAoQVtpXSpBW2ldIC0gKEFbal0qQVtqXSkuY29uaigpKSAqIENvbXAoMCwgLTAuMjUpKyhBW2ldKkJbaV0gLSAoQVtqXSpCW2pdKS5jb25qKCkpICogQ29tcCgwLjUsIDApOwogICAgICAgIEREW2ldID0gKEJbaV0qQltpXSAtIChCW2pdKkJbal0pLmNvbmooKSkgKiBDb21wKDAsIC0wLjI1KTsKICAgIH0KICAgIEZGVChDLCBsZW4sIC0xKTsgRkZUKERELCBsZW4sIC0xKTsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBsZW47ICsraSkgewogICAgICAgICAgIGNbaV0gPSAoKChMTChDW2ldLnJlKzAuNSkgJW1vZCk8PDMwKSVtb2QgICsgKChMTChDW2ldLmltKzAuNSklbW9kICkgPDwxNSklbW9kKyBMTChERFtpXS5yZSswLjUpKSVtb2QgOwoJfQp9CmlubGluZSBpbnQgcmVhZCgpewogICAgaW50IGY9MSx4PTA7Y2hhciBjaD1nZXRjaGFyKCk7CiAgICB3aGlsZSAoY2g8JzAnfHxjaD4nOScpe2lmIChjaD09Jy0nKWY9LTE7Y2g9Z2V0Y2hhcigpO30KICAgIHdoaWxlIChjaD49JzAnJiZjaDw9JzknKXt4PSh4PDwzKSsoeDw8MSkrY2gtJzAnO2NoPWdldGNoYXIoKTt9CiAgICByZXR1cm4gZip4Owp9CiAKaW5saW5lIGludCBxcG93KGludCB4LGludCBwKXtpbnQgYW5zPTE7CiAgICBmb3IoO3A7cD4+PTEseD0xbGwqeCp4JVApaWYocCYxKWFucz0xbGwqYW5zKnglUDsKICAgIHJldHVybiBhbnM7Cn0gCmludCB0ZW1wW21heG5dLGFbbWF4bl0sYlttYXhuXSxjW21heG5dLGRbbWF4bl0sdG1wW21heG5dOwppbmxpbmUgdm9pZCBHZXRJbnYoaW50ICphLGludCAqYixpbnQgbil7CiAgICBpZiAobj09MSkgcmV0dXJuIHZvaWQoYlswXT1xcG93KGFbMF0sUC0yKSk7CiAgICBHZXRJbnYoYSxiLG4+PjEpOwogICAgZm9yIChpbnQgaT0wO2k8bjsrK2kpdG1wW2ldPWFbaV0sdG1wW24raV09MDsKICAgIGludCBrO2ZvciAoaz0xO2s8PW47azw8PTEpOwogICAgZm9yIChpbnQgaT1uO2k8azsrK2kpYltpXT0wOwogICAgQ29udih0bXAsYix0bXAsayk7CiAgICBmb3IoaW50IGk9bjtpPGs7aSsrKQogICAgICB0bXBbaV09MDsKICAgIENvbnYodG1wLGIsdG1wLGspOwogICAgZm9yIChpbnQgaT0wO2k8bjsrK2kpYltpXT0oMipiW2ldJW1vZC10bXBbaV0rbW9kKSVtb2QsYltuK2ldPTA7Cn0KaW5saW5lIHZvaWQgR2V0bG4oaW50ICphLGludCAqYixpbnQgKmMsaW50IG4pewogICAgZm9yIChpbnQgaT0wO2k8bjsrK2kpYltpXT0xbGwqKGkrMSkqYVtpKzFdJVA7CiAgICBHZXRJbnYoYSxjLG4pOwogICAgZm9yIChpbnQgaT0wO2k8bjsrK2kpdG1wW2ldPWNbaV0sdG1wW24raV09MDsKICAgIGludCBrO2ZvciAoaz0xO2s8PW47azw8PTEpOwogICAgQ29udih0bXAsYix0bXAsayk7CiAgICBmb3IgKGludCBpPTE7aTw9bjsrK2kpYltpXT0xbGwqdG1wW2ktMV0qcXBvdyhpLFAtMiklUCxiW2krbl09MDtiWzBdPTA7Cn0KCmlubGluZSB2b2lkIEdldGV4cChpbnQgKmEsaW50ICpiLGludCAqYyxpbnQgKmQsaW50IG4pewogICAgaWYgKG49PTEpcmV0dXJuIHZvaWQoYlswXT0xKTsKICAgIEdldGV4cChhLGIsYyxkLG4+PjEpOwogICAgR2V0bG4oYixjLGQsbik7CiAgICBmb3IgKGludCBpPTA7aTxuOysraSl0bXBbaV09KGFbaV0tY1tpXStQKSVQLHRtcFtuK2ldPTA7Kyt0bXBbMF07CiAgICBpbnQgaztmb3IgKGs9MTtrPD1uO2s8PD0xKTsKICAgIENvbnYodG1wLGIsdG1wLGspOwogICAgZm9yIChpbnQgaT0wO2k8bjsrK2kpYltpXT10bXBbaV0sYltpK25dPTA7Cn0Kdm9pZCBnb3QoaW50IG4saW50IGRlZXApCnsKCWludCBpOwoJaWYobj09MSkKCXsKCSAgICB2ZWNbZGVlcF0ucHVzaF9iYWNrKDEpOwoJCXZlY1tkZWVwXS5wdXNoX2JhY2soMSk7CgkJcmV0dXJuOwoJfQoJZ290KG4+PjEsZGVlcCsxKTsKCXZlY1tkZWVwXS5yZXNpemUobisxKTsKCWludCBkPW4+PjE7Cglmb3IoaT0wO2k8PW47aSsrKQoJewoJCWlmKGk9PTApCgkJICAgZXhbaV09MTsKCQllbHNlCgkJICAgZXhbaV09MUxMKmV4W2ktMV0qZCVtb2Q7IAoJfQoJaW50IGxlbj0xOwoJd2hpbGUobGVuPD1kK2QpCgkgICBsZW48PD0xOwoJZm9yKGk9MDtpPGxlbjtpKyspCgl7CgkgICAgaWYoaTw9KG4+PjEpKQoJICAgIHsKCSAgICAgICBhYVtpXT0xTEwqZXhbKG4+PjEpLWldKmludlsobj4+MSktaV0lbW9kOwoJCSAgIGJiW2ldPTFMTCpmYWNbaV0qdmVjW2RlZXArMV1baV0lbW9kOwoJCX0KCQllbHNlCgkJICAgYmJbaV09YWFbaV09MDsJCgl9CglDb252KGFhLGJiLGNjLGxlbik7Cglmb3IoaT0wO2k8PWQ7aSsrKQoJCWNjW2ldPTFMTCpjY1tpKyhuPj4xKV0qaW52W2ldJW1vZDsKCWZvcihpPWQrMTtpPGxlbjtpKyspCgkgICAgY2NbaV09MDsKCWZvcihpPTA7aTxsZW47aSsrKQoJewoJCWlmKGk8PShuPj4xKSkKCQkgICBhYVtpXT12ZWNbZGVlcCsxXVtpXTsKCQllbHNlCgkJICAgYWFbaV09MDsKCX0KCUNvbnYoYWEsY2MsYmIsbGVuKTsKCWlmKG4mMSkKCXsKCQlmb3IoaT0wO2k8PW47aSsrKQoJCXsKCQkJdmVjW2RlZXBdW2ldPTFMTCpiYltpXSpuJW1vZDsKCQkJdmVjW2RlZXBdW2ldPSh2ZWNbZGVlcF1baV0rYmJbaS0xXSklbW9kOwoJCX0KCX0KCWVsc2UKCXsKCQlmb3IoaT0wO2k8PW47aSsrKQoJCSAgIHZlY1tkZWVwXVtpXT1iYltpXTsKCX0KfQppbnQgQ0MoaW50IG4saW50IG0pCnsKCXJldHVybiAxTEwqZmFjW25dKmludlttXSVtb2QqaW52W24tbV0lbW9kOwp9CmxvbmcgbG9uZyBTLFQ7CmludCBuLG07CmludCBtYWluKCkKewoJSW5pdCgpOwoJc2NhbmYoIiVsbGQlbGxkJWQlZCIsJlMsJlQsJm4sJm0pOwoJaW50IGksaixzLHAscTsKCWZvcihpPTA7aTw9bS1uKzE7aSsrKQoJewoJCWlmKGk9PTApCgkJICBmYWNbaV09MTsKCQllbHNlCgkJICBmYWNbaV09MUxMKmZhY1tpLTFdKmklbW9kOwoJfQoJaW52W20tbisxXT1wb3dlcihmYWNbbS1uKzFdLG1vZC0yKTsKCWZvcihpPW0tbjtpPj0wO2ktLSkKCSAgIGludltpXT0xTEwqaW52W2krMV0qKGkrMSklbW9kOwoJaW50IGxlbj0xOwoJd2hpbGUobGVuPD1tLW4pCgkgICBsZW48PD0xOwogICAgZ290KG0tbiwwKTsKICAgIFM9KFMtKG0tbikrbW9kKSVtb2Q7CiAgICBUJT1tb2Q7CiAgICBtZW1zZXQoYSwwLHNpemVvZihhKSk7CiAgICBtZW1zZXQoYiwwLHNpemVvZihiKSk7CiAgICBmb3IoaT0xO2k8PW0tbjtpKyspCiAgICAJYltpXT1pbnZbaSsxXTsKCWJbMF09MTsKCUdldEludihiLGEsbGVuKTsgIAoJZm9yKGk9MDtpPD1tLW4rMTtpKyspCgl7CgkJaWYoaT09MCkKCQkgICBleFtpXT0xOwoJCWVsc2UKCQkgICBleFtpXT0xTEwqZXhbaS0xXSooVCsxKSVtb2Q7Cgl9Cglmb3IoaT0wO2k8PW0tbjtpKyspCgl7CgkgICAgYltpXT0xTEwqKGV4W2krMV0tMSkqaW52W2krMV0lbW9kOwogICAgICAgIGlmKGJbaV08MCkKICAgICAgICAgICBiW2ldKz1tb2Q7Cgl9Cglmb3IoaT1tLW4rMTtpPGxlbjw8MTtpKyspCgkJYVtpXT1iW2ldPTA7CglDb252KGEsYixmLGxlbjw8MSk7Cglmb3IoaT0wO2k8PW0tbjtpKyspCgl7CgkJZltpXT0xTEwqZltpXSpmYWNbaV0lbW9kOwoJCWlmKGZbaV08MCkKCQkgICBmW2ldKz1tb2Q7Cgl9CgltZW1zZXQoYSwwLHNpemVvZihhKSk7CgltZW1zZXQoYiwwLHNpemVvZihiKSk7CgltZW1zZXQoYywwLHNpemVvZihjKSk7CglpbnQgeCx5OwoJZm9yKGk9MDtpPD1tLW47aSsrKQoJewoJCWFbaV09MUxMKmZbaV0qaW52W2ldJW1vZDsKCQlpZihpJTIpCgkJICAgYVtpXT0obW9kLWFbaV0pJW1vZDsKCQlpZihpPT0wKQoJCXsKCQkJeD1wb3dlcihhW2ldLG1vZC0yKTsKCQkJeT1wb3dlcihhW2ldLG4pOwoJCX0KCQlhW2ldPTFMTCphW2ldKnglbW9kOwoJfQoJR2V0bG4oYSxiLGMsbGVuKTsKCWZvcihpPTA7aTw9bS1uO2krKykKCSAgIGJbaV09MUxMKmJbaV0qbiVtb2Q7Cglmb3IoaT1tLW4rMTtpPGxlbjtpKyspCgkgICBiW2ldPTA7CgltZW1zZXQoYSwwLHNpemVvZihhKSk7CgltZW1zZXQoYywwLHNpemVvZihjKSk7CgltZW1zZXQoZCwwLHNpemVvZihkKSk7CglHZXRleHAoYixhLGMsZCxsZW4pOwoJZm9yKGk9MDtpPD1tLW47aSsrKQoJICAgYVtpXT0xTEwqYVtpXSp5JW1vZDsKCWludCBhd3A9MTsKCWZvcihpPTA7aTw9bS1uO2krKykKCXsKCSAgICBiW2ldPTFMTCphd3AqaW52W2ldJW1vZDsKCSAgICBhd3A9MUxMKmF3cCpTJW1vZDsKCX0KCWZvcihpPW0tbisxO2k8bGVuPDwxO2krKykKCSAgIGFbaV09YltpXT0wOwoJQ29udihhLGIsYyxsZW48PDEpOwoJaW50IGFucz0wOwoJZm9yKGk9MDtpPD1tLW47aSsrKQoJCWFucz0oYW5zKzFMTCpjW2ldKnZlY1swXVtpXSVtb2QqZmFjW2ldKSVtb2Q7CglhbnM9MUxMKmFucyppbnZbbS1uXSVtb2Q7CglwcmludGYoIiVkXG4iLGFucyk7CglyZXR1cm4gMDsKfQo=