#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define nl '\n'
//#define int long long
int mod = 1e9 + 7;
ll fpow(ll n, ll k)
{
if (k == 0)
return 1;
ll res = fpow(n, k / 2) % mod;
res = ((res % mod) * (res % mod)) % mod;
if (k % 2 == 1)
res = ((res % mod) * (n % mod)) % mod;
return res;
}
int modInverse(int a, int mod)
{
return fpow(a, mod - 2);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgIGxsIGxvbmcgbG9uZwojZGVmaW5lICBubCAnXG4nCi8vI2RlZmluZSAgaW50IGxvbmcgbG9uZwppbnQgbW9kID0gMWU5ICsgNzsKCmxsIGZwb3cobGwgbiwgbGwgaykKewogICAgaWYgKGsgPT0gMCkKICAgICAgICByZXR1cm4gMTsKICAgIGxsIHJlcyA9IGZwb3cobiwgayAvIDIpICUgbW9kOwogICAgcmVzID0gKChyZXMgJSBtb2QpICogKHJlcyAlIG1vZCkpICUgbW9kOwogICAgaWYgKGsgJSAyID09IDEpCiAgICAgICAgcmVzID0gKChyZXMgJSBtb2QpICogKG4gJSBtb2QpKSAlIG1vZDsKICAgIHJldHVybiByZXM7Cn0KCmludCBtb2RJbnZlcnNlKGludCBhLCBpbnQgbW9kKQp7CiAgICByZXR1cm4gZnBvdyhhLCBtb2QgLSAyKTsKfQoKc2lnbmVkIG1haW4oKQp7CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbygwKTsKICAgIGNpbi50aWUoMCk7CiAgICBjb3V0LnRpZSgwKTsKCgogICAgcmV0dXJuIDA7Cn0K