#include <bits/stdc++.h>
using namespace std; 
 
// Cho 3 số nguyên a, b, c   
// nếu a đồng dư b (mod c) thì có nghĩa là: a và b có cùng số dư khi mod cho c   
 
// Ví dụ: 
// Cho c = 3 
// thì ta có:  
// 5 đồng dư với 8 (mod 3)   
 
// 5 mod 3 = 2   
// 8 mod 3 = 2   
 
// a, b có thể rất lớn (<= 1e18), kiểu dữ liệu long long, nhưng c thì tầm <= 1e9   
// (a + b) % c = [(a % c) + (b % c)] % c  
// (a - b) % c = [(a % c) - (b % c) + c] % c  
// (a * b) % c = [(a % c) * (b % c)] % c  
// (a / b) % c = 
 
// [a * (1 / b)] % c
// phải tìm được một thằng x mà đồng dư với (1/b) (mod c) 
// => (a * x) % c  
 
// tìm nghịch đảo module của b (mod c): 
// nếu c nguyên tố: b^(c - 2) (mod c) 
 
// với p nguyên tố: 
// a^(p - 1) = 1 (mod p) (định lí Fermat nhỏ)  
// nhân 2 vế với a^(-1) ta có:  
// a^(p-2) = a^(-1) (mod p)  
 
// một số tính chất của đồng dư: 
//      a     = b     (moc c)   
// <=>  a + d = b + d (mod c)   
// <=>  a - d = b - d (mod c)   
// <=>  a * d = b * d (mod c)   
// <=>  a / d = b / d (mod c) [điều kiện gcd(d, c) = 1] 
 
//     a     = b (mod c) 
// <=> a - b = 0 (mod c) 
// =>  a - b chia hết cho c hay c là ước của a - b   
 
//     a = x (mod b) 
// <=> a = k * b + x (k thuộc Z) 
 
// 8 = 2 (mod 3)
// 8 = 2 * 3 + 2   
 
// a mob b = a - [a / b] * b  
 
#define int long long  
 
signed main() {
	ios::sync_with_stdio(0); cin.tie(0);   
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7IAoKLy8gQ2hvIDMgc+G7kSBuZ3V5w6puIGEsIGIsIGMgICAKLy8gbuG6v3UgYSDEkeG7k25nIGTGsCBiIChtb2QgYykgdGjDrCBjw7MgbmdoxKlhIGzDoDogYSB2w6AgYiBjw7MgY8O5bmcgc+G7kSBkxrAga2hpIG1vZCBjaG8gYyAgIAoKLy8gVsOtIGThu6U6IAovLyBDaG8gYyA9IDMgCi8vIHRow6wgdGEgY8OzOiAgCi8vIDUgxJHhu5NuZyBkxrAgduG7m2kgOCAobW9kIDMpICAgCgovLyA1IG1vZCAzID0gMiAgIAovLyA4IG1vZCAzID0gMiAgIAoKLy8gYSwgYiBjw7MgdGjhu4MgcuG6pXQgbOG7m24gKDw9IDFlMTgpLCBraeG7g3UgZOG7ryBsaeG7h3UgbG9uZyBsb25nLCBuaMawbmcgYyB0aMOsIHThuqdtIDw9IDFlOSAgIAovLyAoYSArIGIpICUgYyA9IFsoYSAlIGMpICsgKGIgJSBjKV0gJSBjICAKLy8gKGEgLSBiKSAlIGMgPSBbKGEgJSBjKSAtIChiICUgYykgKyBjXSAlIGMgIAovLyAoYSAqIGIpICUgYyA9IFsoYSAlIGMpICogKGIgJSBjKV0gJSBjICAKLy8gKGEgLyBiKSAlIGMgPSAKCi8vIFthICogKDEgLyBiKV0gJSBjCi8vIHBo4bqjaSB0w6xtIMSRxrDhu6NjIG3hu5l0IHRo4bqxbmcgeCBtw6AgxJHhu5NuZyBkxrAgduG7m2kgKDEvYikgKG1vZCBjKSAKLy8gPT4gKGEgKiB4KSAlIGMgIAoKLy8gdMOsbSBuZ2jhu4tjaCDEkeG6o28gbW9kdWxlIGPhu6dhIGIgKG1vZCBjKTogCi8vIG7hur91IGMgbmd1ecOqbiB04buROiBiXihjIC0gMikgKG1vZCBjKSAKCi8vIHbhu5tpIHAgbmd1ecOqbiB04buROiAKLy8gYV4ocCAtIDEpID0gMSAobW9kIHApICjEkeG7i25oIGzDrSBGZXJtYXQgbmjhu48pICAKLy8gbmjDom4gMiB24bq/IHbhu5tpIGFeKC0xKSB0YSBjw7M6ICAKLy8gYV4ocC0yKSA9IGFeKC0xKSAobW9kIHApICAKCi8vIG3hu5l0IHPhu5EgdMOtbmggY2jhuqV0IGPhu6dhIMSR4buTbmcgZMawOiAKLy8gICAgICBhICAgICA9IGIgICAgIChtb2MgYykgICAKLy8gPD0+ICBhICsgZCA9IGIgKyBkIChtb2QgYykgICAKLy8gPD0+ICBhIC0gZCA9IGIgLSBkIChtb2QgYykgICAKLy8gPD0+ICBhICogZCA9IGIgKiBkIChtb2QgYykgICAKLy8gPD0+ICBhIC8gZCA9IGIgLyBkIChtb2QgYykgW8SRaeG7gXUga2nhu4duIGdjZChkLCBjKSA9IDFdIAoKLy8gICAgIGEgICAgID0gYiAobW9kIGMpIAovLyA8PT4gYSAtIGIgPSAwIChtb2QgYykgCi8vID0+ICBhIC0gYiBjaGlhIGjhur90IGNobyBjIGhheSBjIGzDoCDGsOG7m2MgY+G7p2EgYSAtIGIgICAKCi8vICAgICBhID0geCAobW9kIGIpIAovLyA8PT4gYSA9IGsgKiBiICsgeCAoayB0aHXhu5ljIFopIAoKLy8gOCA9IDIgKG1vZCAzKQovLyA4ID0gMiAqIDMgKyAyICAgCgovLyBhIG1vYiBiID0gYSAtIFthIC8gYl0gKiBiICAKCiNkZWZpbmUgaW50IGxvbmcgbG9uZyAgCgpzaWduZWQgbWFpbigpIHsKCWlvczo6c3luY193aXRoX3N0ZGlvKDApOyBjaW4udGllKDApOyAgIAp9