using u64 = unsigned long long; using u128 = unsigned __int128; const u64 MOD = (1ULL << 61) - 1; u64 mul(u64 a, u64 b) { u128 t = (u128)(a) * b; t = (t >> 61) + (t & MOD); return (t >= MOD) ? t - MOD : t; } u64 mul2(u64 a8, u64 b8) { u128 c = (u128)(a8) * b8; u64 x = (…