// https://yukicoder.me/problems/448
pub use __cargo_equip::prelude::*;

use iolib::scan;
use math::garner_prechecked;

const MOD: i64 = 1000_000_007;

fn main() {
    scan!(n: usize, p: [(i64, i64); n]);

    let (a, p) = p.into_iter().unzip::<i64, i64, Vec<_>, Vec<_>>();

    let f = a.iter().all(|a| *a == 0);

    if let Some((res, lcm)) = garner_prechecked(&a, &p, MOD) {
        if f {
            println!("{}", lcm)
        } else {
            println!("{}", res)
        }
    } else {
        println!("-1")
    }
}

#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod iolib {
            pub use crate::__cargo_equip::macros::iolib::*;
            mod input {
                use std::io::{BufRead, Read, StdinLock};
                use std::ptr::copy_nonoverlapping;
                use std::slice::from_raw_parts_mut;

                const BUF_SIZE: usize = 1 << 18;

                pub struct FastInput {
                    head: usize,
                    tail: usize,
                    interactive: bool,
                    eof: bool,
                    buf: [u8; BUF_SIZE],
                }

                impl FastInput {
                    pub const fn new() -> Self {
                        Self {
                            head: 0,
                            tail: 0,
                            interactive: false,
                            eof: false,
                            buf: [0; 1 << 18],
                        }
                    }

                    #[inline]
                    pub fn set_interactive(&mut self) { self.interactive = true; }

                    #[inline]
                    unsafe fn load(&mut self) {
                        // BUF: [buf_head............head....tail...]
                        let buf_head = self.buf.as_mut_ptr();
                        // src = buf_head + head
                        // so, src = &head
                        let src = buf_head.add(self.head);
                        let count = self.tail - self.head;
                        // <before>
                        // BUF: [buf_head............[head....tail]...]
                        //          ^        copy       |
                        //          |___________________|
                        // <after>
                        // BUF: [[head....tail].............[head....tail]...]
                        copy_nonoverlapping(src, buf_head, count);
                        // let buf = from_raw_parts_mut(buf_head.add(count), BUF_SIZE - count);
                        // self.tail = count + STDIN_SOURCE().read(buf).unwrap();
                        self.tail = count
                            + if !self.interactive {
                                let buf = from_raw_parts_mut(buf_head.add(count), BUF_SIZE - count);
                                let res = STDIN_SOURCE().read(buf).unwrap();
                                self.eof |= res == 0;
                                res
                            } else {
                                let mut buf = vec![];
                                let res = STDIN_SOURCE().read_until(b'\n', &mut buf).unwrap();
                                copy_nonoverlapping(buf.as_ptr(), buf_head.add(count), res);
                                res
                            };
                        self.head = 0;
                        if self.tail < BUF_SIZE {
                            self.buf[self.tail] = b' ';
                        }
                    }

                    #[inline]
                    fn readc(&mut self) -> u8 {
                        let res = self.buf[self.head];
                        self.head += 1;
                        res
                    }

                    #[inline(always)]
                    fn refill_buffer(&mut self) {
                        if self.eof {
                            return;
                        }
                        if !self.interactive && self.head + 32 > self.tail {
                            unsafe { self.load() }
                        } else if self.interactive && self.head >= self.tail {
                            unsafe { self.load() }
                        }
                    }

                    #[inline]
                    pub fn read_u64(&mut self) -> u64 {
                        self.refill_buffer();

                        let mut x = 0u64;
                        while !self.buf[self.head].is_ascii_whitespace() {
                            x = x * 10 + (self.buf[self.head] - b'0') as u64;
                            self.head += 1;
                        }
                        self.head += 1;
                        x
                    }

                    #[inline]
                    pub fn read_i64(&mut self) -> i64 {
                        self.refill_buffer();

                        if self.buf[self.head] == b'-' {
                            self.head += 1;
                            -(self.read_u64() as i64)
                        } else {
                            self.read_u64() as i64
                        }
                    }

                    #[inline]
                    pub fn read_char(&mut self) -> char {
                        self.refill_buffer();

                        let c = self.readc();
                        if self.buf[self.head].is_ascii_whitespace() {
                            self.head += 1;
                        }

                        c as char
                    }

                    #[inline]
                    pub fn read_string(&mut self) -> String {
                        if self.interactive {
                            let mut buf = String::new();
                            std::io::BufReader::read_line(&mut std::io::BufReader::new(unsafe { STDIN_SOURCE() }), &mut buf).unwrap();
                            return buf;
                        }

                        self.refill_buffer();

                        let mut tail = self.head;
                        while tail < self.tail && !self.buf[tail].is_ascii_whitespace() {
                            tail += 1;
                        }

                        let mut res = String::from_utf8_lossy(&self.buf[self.head..tail]).into_owned();

                        self.head = tail;

                        if tail == self.tail {
                            res.push_str(&self.read_string());
                        } else {
                            self.head += 1;
                        }

                        res
                    }
                }

                macro_rules! impl_read_signed_integeer {
                    ( $( { $t:ty, $fname:ident } )* ) => {
                        $(impl FastInput {
                            #[inline]
                            pub fn $fname(&mut self) -> $t { self.read_i64() as $t }
                        })*
                    };
                }

                macro_rules! impl_read_unsigned_integeer {
                    ( $( { $t:ty, $fname:ident } )* ) => {
                        $(impl FastInput {
                            #[inline]
                            pub fn $fname (&mut self) -> $t { self.read_u64() as $t }
                        })*
                    };
                }

                impl_read_signed_integeer!({i8, read_i8} {i16, read_i16} {i32, read_i32} {i128, read_i128} {isize, read_isize});
                impl_read_unsigned_integeer!({u8, read_u8} {u16, read_u16} {u32, read_u32} {u128, read_u128} {usize, read_usize});

                fn init() -> &'static mut StdinLock<'static> {
                    let stdin = Box::leak(Box::new(std::io::stdin()));
                    unsafe {
                        STDIN = Box::leak(Box::new(stdin.lock()));
                        STDIN_SOURCE = get_stdin_source
                    }

                    get_stdin_source()
                }

                #[inline(always)]
                fn get_stdin_source() -> &'static mut StdinLock<'static> { unsafe { STDIN.as_mut().unwrap() } }

                static mut INPUT: FastInput = FastInput::new();
                static mut STDIN: *mut StdinLock<'static> = 0 as *mut StdinLock<'static>;
                static mut STDIN_SOURCE: fn() -> &'static mut StdinLock<'static> = init;

                pub fn get_input() -> &'static mut FastInput { unsafe { &mut INPUT } }
                pub fn set_interactive() { unsafe { INPUT.set_interactive() } }
            }

            pub use input::{get_input, set_interactive};

            #[macro_export]
            macro_rules! __cargo_equip_macro_def_iolib_scan {
                // Terminator
                ( $(, )? ) => {};
                // Vec<Vec<....>>, ......
                ( $v: ident : [ [ $( $inner:tt )+ ] ; $len:expr ] $(, $( $rest:tt )* )? ) => {
                    let $v = (0..$len).map(|_| { $crate::__cargo_equip::crates::iolib::scan!(w: [ $( $inner )+ ]); w }).collect::<Vec<_>>();
                    $( $crate::__cargo_equip::crates::iolib::scan!($( $rest )*); )?
                };
                // Vec<$t>, .....
                ( $v:ident : [ $t:tt ; $len:expr ] $(, $( $rest:tt )* )? ) => {
                    let $v = (0..$len).map(|_| { $crate::__cargo_equip::crates::iolib::scan!($v : $t); $v }).collect::<Vec<_>>();
                    $( $crate::__cargo_equip::crates::iolib::scan!($( $rest )*); )?
                };
                // Expand tuple
                ( @expandtuple, ( $t:tt )) => {
                    { $crate::__cargo_equip::crates::iolib::scan!(w: $t); w }
                };
                // Expand tuple
                ( @expandtuple, ( $t:tt $(, $rest:tt )* ) ) => {
                    (
                        $crate::__cargo_equip::crates::iolib::scan!(@expandtuple, ( $t ))
                        $(, $crate::__cargo_equip::crates::iolib::scan!(@expandtuple, ( $rest )) )*
                    )
                };
                // let $v: ($t, $u, ....) = (.......)
                ( $v:ident : ( $( $rest:tt )* ) ) => {
                    let $v = $crate::__cargo_equip::crates::iolib::scan!(@expandtuple, ( $( $rest )* ));
                };
                // let $v: $t = ......, .......
                ( $v:ident : $t:tt $(, $( $rest:tt )* )? ) => {
                    $crate::__cargo_equip::crates::iolib::read_value!($v : $t);
                    $( $crate::__cargo_equip::crates::iolib::scan!($( $rest )*); )?
                };
                // ......
                ( $( $rest:tt )* ) => {
                    $crate::__cargo_equip::crates::iolib::scan!($( $rest )*);
                };
            }
            macro_rules! scan {
                ($($tt:tt)*) => (crate::__cargo_equip_macro_def_iolib_scan!{$($tt)*});
            }

            #[macro_export]
            macro_rules! __cargo_equip_macro_def_iolib_scani {
                ( $( $rest:tt )* ) => {
                    $crate::__cargo_equip::crates::iolib::set_interactive();
                    $crate::__cargo_equip::crates::iolib::scan!( $( $rest )* );
                };
            }
            macro_rules! scani {
                ($($tt:tt)*) => (crate::__cargo_equip_macro_def_iolib_scani!{$($tt)*});
            }

            #[macro_export]
            macro_rules! __cargo_equip_macro_def_iolib_read_value {
                ( $v:ident : i8 ) => {
                    let $v = $crate::__cargo_equip::crates::iolib::get_input().read_i8();
                };
                ( $v:ident : i16 ) => {
                    let $v = $crate::__cargo_equip::crates::iolib::get_input().read_i16();
                };
                ( $v:ident : i32 ) => {
                    let $v = $crate::__cargo_equip::crates::iolib::get_input().read_i32();
                };
                ( $v:ident : i64 ) => {
                    let $v = $crate::__cargo_equip::crates::iolib::get_input().read_i64();
                };
                ( $v:ident : i128 ) => {
                    let $v = $crate::__cargo_equip::crates::iolib::get_input().read_i128();
                };
                ( $v:ident : isize ) => {
                    let $v = $crate::__cargo_equip::crates::iolib::get_input().read_isize();
                };
                ( $v:ident : u8 ) => {
                    let $v = $crate::__cargo_equip::crates::iolib::get_input().read_u8();
                };
                ( $v:ident : u16 ) => {
                    let $v = $crate::__cargo_equip::crates::iolib::get_input().read_u16();
                };
                ( $v:ident : u32 ) => {
                    let $v = $crate::__cargo_equip::crates::iolib::get_input().read_u32();
                };
                ( $v:ident : u64 ) => {
                    let $v = $crate::__cargo_equip::crates::iolib::get_input().read_u64();
                };
                ( $v:ident : u128 ) => {
                    let $v = $crate::__cargo_equip::crates::iolib::get_input().read_u128();
                };
                ( $v:ident : usize ) => {
                    let $v = $crate::__cargo_equip::crates::iolib::get_input().read_usize();
                };
                ( $v:ident : char ) => {
                    let $v = $crate::__cargo_equip::crates::iolib::get_input().read_char();
                };
                ( $v:ident : String ) => {
                    let $v = $crate::__cargo_equip::crates::iolib::get_input().read_string();
                };
                ( $v:ident : $t:ty ) => {
                    let $v: $t = $crate::__cargo_equip::crates::iolib::get_input()
                        .read_string()
                        .parse()
                        .unwrap();
                };
            }
            macro_rules! read_value {
                ($($tt:tt)*) => (crate::__cargo_equip_macro_def_iolib_read_value!{$($tt)*});
            }
        }

        pub mod math {
            use crate::__cargo_equip::preludes::math::*;
            use numeric::Integer;

            //////////////////////////////////////////////////////////////////////////////////
            // Define famous functions for integers
            //////////////////////////////////////////////////////////////////////////////////

            /// Return gcd(x, y).
            #[inline]
            pub fn gcd<T: Integer>(mut x: T, mut y: T) -> T {
                while y != T::zero() {
                    let (nx, ny) = (y, x % y);
                    x = nx;
                    y = ny;
                }
                x
            }

            /// Return lcm(x, y).
            #[inline]
            pub fn lcm<T: Integer>(x: T, y: T) -> T { x / gcd(x, y) * y }

            /// Solve the equation "ax + by = gcd(a, b)"
            /// Return (gcd(a, b), x, y)
            //  s * 1 + t * 0 = s    ...(1)  (sx = 1, sy = 0)
            //  s * 0 + t * 1 = t    ...(2)  (tx = 0, ty = 1)
            //       -> (1) - (2) * |s/t|
            //       -> s * (sx - tx * |s/t|) + t * (sy - ty * |s/t|) = s % t
            // Repeating this, the right-hand side becomes gcd(s, t)
            //  s * tx + t * ty = gcd(s, t)
            #[inline]
            pub fn ext_gcd<T: Integer>(a: T, b: T) -> (T, T, T) {
                let (mut s, mut t) = (a, b);
                let (mut sx, mut tx) = (T::one(), T::zero());
                let (mut sy, mut ty) = (T::zero(), T::one());
                while s % t != T::zero() {
                    let d = s / t;

                    let u = s % t;
                    let ux = sx - tx * d;
                    let uy = sy - ty * d;
                    s = t;
                    sx = tx;
                    sy = ty;
                    t = u;
                    tx = ux;
                    ty = uy;
                }

                (t, tx, ty)
            }

            /// Using p as the modulus, calculate a^n.
            #[inline]
            pub fn mod_pow(a: i64, mut n: i64, p: i64) -> i64 {
                let mut res = 1;
                let mut pow = a;
                while n != 0 {
                    if n & 1 != 0 {
                        res = (res as i128 * pow as i128 % p as i128) as i64;
                    }
                    pow = (pow as i128 * pow as i128 % p as i128) as i64;
                    n >>= 1;
                }
                res
            }

            /// Return an integer x less than lcm(m1, m2) satisfying x = a (mod m1) and x = b (mod m2) and lcm(m1, m2).
            /// If no integers satisfy the condition, return None.
            //      m1 = gcd(m1, m2) * p,   m2 = gcd(m1, m2) * q
            //          -> x = a (mod gcd(m1, m2)) && x = b (mod gcd(m1, m2))
            //      m1 * k + m2 * l = gcd(m1, m2) = d
            //          -> now, * s (= (b - a) / d)
            //      s * m1 * k + s * m2 * l = b - a
            //          -> a + s * m1 * k = b - s * m2 * l = x
            //          -> x = a (mod m1) && x = b (mod m2)
            #[inline]
            pub fn chinese_remainder_theorem(mut a: i64, mut m1: i64, mut b: i64, mut m2: i64) -> Option<(i64, i64)> {
                if m1 < m2 {
                    std::mem::swap(&mut a, &mut b);
                    std::mem::swap(&mut m1, &mut m2);
                }
                let (a, b) = (a.rem_euclid(m1), b.rem_euclid(m2));
                if m1 % m2 == 0 {
                    return if a % m2 != b { None } else { Some((a, m1)) };
                }

                let (d, k, _) = ext_gcd(m1, m2);
                let u1 = m2 / d;

                if a % d != b % d {
                    return None;
                }

                let x = (b - a) / d % u1 * k % u1;
                let m = m1 * u1;
                let res = (a + x * m1).rem_euclid(m);
                Some((res, m))
            }

            /// Return a minimum integer x (mod modulo) satisfying x = a[i] (mod p[i]) for any i and p[1]*p[2]*p[3].... (mod modulo)
            /// Note: For any i, j (i != j), gcd(p[i], p[j]) MUST be 1.
            //      x = t1 + t2p1 + t3p1p2 + t4p1p2p3 + ...
            //          x  = a1 (mod p1)
            //              -> a1 = x % p1 = t1 (mod p1)
            //          x  = a2 (mod p2)
            //              -> a2 = x % p2 = t1 + t2p1 (mod p2)
            //              -> t2 = (a2 - t1) * p1^{-1} (mod p2)
            //          ... so, t[k] = ((...((a[k] - t[1])p[1,k]^{-1} - t[2])p[2,k]^{-1} - ...)p[k-2,k]^{-1} - t[k-1]))p[k-1,k]^{-1} (mod p[k])
            //                       = a[k]p[1,k]^{-1}p[2,k]^{-1}...p[k-1,k]^{-1} - t[1]p[1,k]^{-1}p[2,k]^{-1}...p[k-1,k]^{-1} - t[2]p[2,k]^{-1}p[3,k]^{-1}...p[k-1,k]^{-1} - ... - t[k-1]p[k-1,k]^{-1}
            //                       = a[k](p[1,k]p[2,k]...p[k-1,k])^{-1} - t[1](p[1,k]p[2,k]...p[k-1,k])^{-1} - t[2](p[2,k]p[3,k]...p[k-1,k])^{-1} - ... - t[k-1]p[k-1,k]^{-1}
            //                       = (a[k] - x[..k]) * (p[1,k]p[2,k]p[3,k]...p[k-1,k])^{-1}
            //                       = (a[k] - res[k]) * prod[k]^{-1}
            #[inline]
            pub fn garner(a: &[i64], p: &[i64], modulo: i64) -> (i64, i64) {
                assert_eq!(a.len(), p.len());
                // prod[i] = p[0]p[1]...p[i-1]
                // res[i]  = t[0] + t[1]p[0] + t[2]p[0]p[1] + ... t[i-1]p[0]p[1]...p[i-2]
                let mut prod = vec![1; p.len() + 1];
                let mut res = vec![0; p.len() + 1];
                for (i, (&a, &m)) in a.iter().zip(p.iter()).enumerate() {
                    let a = a % m;
                    let (_, inv, _) = ext_gcd(prod[i], m);
                    let t = ((a - res[i]) * inv).rem_euclid(m);
                    for (i, &p) in p.iter().enumerate().skip(i + 1) {
                        res[i] = (res[i] + (t * prod[i])) % p;
                        prod[i] = (prod[i] * m) % p;
                    }
                    res[p.len()] = (res[p.len()] + (t * prod[p.len()])) % modulo;
                    prod[p.len()] = (prod[p.len()] * m) % modulo;
                }
                (res[p.len()], prod[p.len()])
            }

            /// Return a minimum integer x (mod modulo) satisfying x = a[i] (mod p[i]) for any i and p[1]*p[2]*p[3].... (mod modulo)
            /// For any i, j (i != j), gcd(p[i], p[j]) = 1 is not required.
            /// If the condition is inconsistent and no solution exists, return None.
            #[inline]
            pub fn garner_prechecked(a: &[i64], p: &[i64], modulo: i64) -> Option<(i64, i64)> {
                let mut p = p.to_vec();
                for i in 0..a.len() {
                    for j in 0..i {
                        let mut g = gcd(p[i], p[j]);

                        if (a[i] - a[j]) % g != 0 {
                            return None;
                        }

                        p[i] /= g;
                        p[j] /= g;

                        let mut gi = gcd(p[i], g);
                        let mut gj = g / gi;

                        g = gcd(gi, gj);
                        gi *= g;
                        gj /= g;
                        while g != 1 {
                            g = gcd(gi, gj);
                            gi *= g;
                            gj /= g;
                        }

                        p[i] *= gi;
                        p[j] *= gj;
                    }
                }

                Some(garner(a, &p, modulo))
            }
        }

        pub mod numeric {
            pub mod float {
                use super::Numeric;
                use std::ops::Neg;

                macro_rules! impl_numeric_trait_for_float {
                    ( $( $t:tt )* ) => {
                        $(impl Numeric for $t {
                            fn max_value() -> Self { std::$t::MAX }
                            fn min_value() -> Self { std::$t::MIN }
                        })*
                    };
                }

                impl_numeric_trait_for_float!(f32 f64);

                pub trait Float: Numeric + Neg<Output = Self> {
                    fn abs(self) -> Self;
                    fn acos(self) -> Self;
                    fn asin(self) -> Self;
                    fn atan(self) -> Self;
                    fn atan2(self, other: Self) -> Self;
                    fn cbrt(self) -> Self;
                    fn ceil(self) -> Self;
                    fn cos(self) -> Self;
                    fn div_euclid(self, rhs: Self) -> Self;
                    fn floor(self) -> Self;
                    fn hypot(self, other: Self) -> Self;
                    fn is_finite(self) -> bool;
                    fn is_infinite(self) -> bool;
                    fn is_nan(self) -> bool;
                    fn is_sign_negative(self) -> bool;
                    fn is_sign_positive(self) -> bool;
                    fn max(self, other: Self) -> Self;
                    fn min(self, other: Self) -> Self;
                    fn mul_add(self, a: Self, b: Self) -> Self;
                    fn powf(self, n: Self) -> Self;
                    fn powi(self, n: i32) -> Self;
                    fn rem_euclid(self, rhs: Self) -> Self;
                    fn round(self) -> Self;
                    fn signum(self) -> Self;
                    fn sin(self) -> Self;
                    fn sin_cos(self) -> (Self, Self);
                    fn sqrt(self) -> Self;
                    fn tan(self) -> Self;
                    fn to_radians(self) -> Self;
                    fn pi() -> Self;
                }

                macro_rules! impl_float_trait {
                    ( $( $t:tt )* ) => {
                        $(impl Float for $t {
                            fn abs(self) -> Self { self.abs() }
                            fn acos(self) -> Self { self.acos() }
                            fn asin(self) -> Self { self.asin() }
                            fn atan(self) -> Self { self.atan() }
                            fn atan2(self, other: Self) -> Self { self.atan2(other) }
                            fn cbrt(self) -> Self { self.cbrt() }
                            fn ceil(self) -> Self { self.ceil() }
                            fn cos(self) -> Self { self.cos() }
                            fn div_euclid(self, rhs: Self) -> Self { self.div_euclid(rhs) }
                            fn floor(self) -> Self { self.floor() }
                            fn hypot(self, other: Self) -> Self { self.hypot(other) }
                            fn is_finite(self) -> bool { self.is_finite() }
                            fn is_infinite(self) -> bool { self.is_infinite() }
                            fn is_nan(self) -> bool { self.is_nan() }
                            fn is_sign_negative(self) -> bool { self.is_sign_negative() }
                            fn is_sign_positive(self) -> bool { self.is_sign_positive() }
                            fn max(self, other: Self) -> Self { self.max(other) }
                            fn min(self, other: Self) -> Self { self.min(other) }
                            fn mul_add(self, a: Self, b: Self) -> Self { self.mul_add(a, b) }
                            fn powf(self, n: Self) -> Self { self.powf(n) }
                            fn powi(self, n: i32) -> Self { self.powi(n) }
                            fn rem_euclid(self, rhs: Self) -> Self { self.rem_euclid(rhs) }
                            fn round(self) -> Self { self.round() }
                            fn signum(self) -> Self { self.signum() }
                            fn sin(self) -> Self { self.sin() }
                            fn sin_cos(self) -> (Self, Self) { self.sin_cos() }
                            fn sqrt(self) -> Self { self.sqrt() }
                            fn tan(self) -> Self { self.tan() }
                            fn to_radians(self) -> Self { self.to_radians() }
                            fn pi() -> Self { std::$t::consts::PI }
                        })*
                    };
                }

                impl_float_trait!(f32 f64);
            }
            pub mod integer {
                use super::Numeric;
                use std::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign};

                macro_rules! impl_numeric_trait_for_integer {
                    ( $( $t:tt )* ) => {
                        $(impl Numeric for $t {
                            fn max_value() -> Self { std::$t::MAX }
                            fn min_value() -> Self { std::$t::MIN }
                        })*
                    };
                }

                impl_numeric_trait_for_integer!(i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize);

                pub trait Integer:
                    Numeric
                    + Rem<Self, Output = Self>
                    + RemAssign
                    + Shl<i32, Output = Self>
                    + Shl<i64, Output = Self>
                    + Shl<u32, Output = Self>
                    + Shl<u64, Output = Self>
                    + Shl<usize, Output = Self>
                    + Shr<i32, Output = Self>
                    + Shr<i64, Output = Self>
                    + Shr<u32, Output = Self>
                    + Shr<u64, Output = Self>
                    + Shr<usize, Output = Self>
                    + ShlAssign<i32>
                    + ShlAssign<i64>
                    + ShlAssign<u32>
                    + ShlAssign<u64>
                    + ShlAssign<usize>
                    + ShrAssign<i32>
                    + ShrAssign<i64>
                    + ShrAssign<u32>
                    + ShrAssign<u64>
                    + ShrAssign<usize>
                    + BitAnd<Self, Output = Self>
                    + BitOr<Self, Output = Self>
                    + BitXor<Self, Output = Self>
                    + BitAndAssign
                    + BitOrAssign
                    + BitXorAssign
                    + std::hash::Hash
                    + Eq
                    + Ord
                {
                    fn abs_diff(self, other: Self) -> Self;
                    fn count_ones(self) -> u32;
                    fn count_zeros(self) -> u32;
                    fn div_euclid(self, rhs: Self) -> Self;
                    fn leading_ones(self) -> u32;
                    fn leading_zeros(self) -> u32;
                    fn rem_euclid(self, rhs: Self) -> Self;
                    fn reverse_bits(self) -> Self;
                    fn rotate_left(self, n: u32) -> Self;
                    fn rotate_right(self, n: u32) -> Self;
                    fn trailing_ones(self) -> u32;
                    fn trailing_zeros(self) -> u32;
                    fn overflowing_add(self, rhs: Self) -> (Self, bool);
                    fn overflowing_mul(self, rhs: Self) -> (Self, bool);
                    fn overflowing_neg(self) -> (Self, bool);
                    fn overflowing_shl(self, rhs: u32) -> (Self, bool);
                    fn overflowing_shr(self, rhs: u32) -> (Self, bool);
                    fn overflowing_sub(self, rhs: Self) -> (Self, bool);
                    fn saturating_add(self, rhs: Self) -> Self;
                    fn saturating_mul(self, rhs: Self) -> Self;
                    fn saturating_sub(self, rhs: Self) -> Self;
                    fn wrapping_add(self, rhs: Self) -> Self;
                    fn wrapping_mul(self, rhs: Self) -> Self;
                    fn wrapping_neg(self) -> Self;
                    fn wrapping_shl(self, rhs: u32) -> Self;
                    fn wrapping_shr(self, rhs: u32) -> Self;
                    fn wrapping_sub(self, rhs: Self) -> Self;
                }

                macro_rules! impl_integer_trait {
                    ( $( $t:ty )* ) => {
                        $(impl Integer for $t {
                            fn abs_diff(self, other: Self) -> Self { std::cmp::max(self, other) - std::cmp::min(self, other) }
                            fn count_ones(self) -> u32 { self.count_ones() }
                            fn count_zeros(self) -> u32 { self.count_zeros() }
                            fn div_euclid(self, rhs: Self) -> Self { self.div_euclid(rhs) }
                            fn leading_ones(self) -> u32 { (!self).leading_zeros() }
                            fn leading_zeros(self) -> u32 { self.leading_zeros() }
                            fn rem_euclid(self, rhs: Self) -> Self { self.rem_euclid(rhs) }
                            fn reverse_bits(self) -> Self { self.reverse_bits() }
                            fn rotate_left(self, n: u32) -> Self { self.rotate_left(n) }
                            fn rotate_right(self, n: u32) -> Self { self.rotate_right(n) }
                            fn trailing_ones(self) -> u32 { (!self).trailing_zeros() }
                            fn trailing_zeros(self) -> u32 { self.trailing_zeros() }
                            fn overflowing_add(self, rhs: Self) -> (Self, bool) { self.overflowing_add(rhs) }
                            fn overflowing_mul(self, rhs: Self) -> (Self, bool) { self.overflowing_mul(rhs) }
                            fn overflowing_neg(self) -> (Self, bool) { self.overflowing_neg() }
                            fn overflowing_shl(self, rhs: u32) -> (Self, bool) { self.overflowing_shl(rhs) }
                            fn overflowing_shr(self, rhs: u32) -> (Self, bool) { self.overflowing_shr(rhs) }
                            fn overflowing_sub(self, rhs: Self) -> (Self, bool) { self.overflowing_sub(rhs) }
                            fn saturating_add(self, rhs: Self) -> Self { self.saturating_add(rhs) }
                            fn saturating_mul(self, rhs: Self) -> Self { self.saturating_mul(rhs) }
                            fn saturating_sub(self, rhs: Self) -> Self { self.saturating_sub(rhs) }
                            fn wrapping_add(self, rhs: Self) -> Self { self.wrapping_add(rhs) }
                            fn wrapping_mul(self, rhs: Self) -> Self { self.wrapping_mul(rhs) }
                            fn wrapping_neg(self) -> Self { self.wrapping_neg() }
                            fn wrapping_shl(self, rhs: u32) -> Self { self.wrapping_shl(rhs) }
                            fn wrapping_shr(self, rhs: u32) -> Self { self.wrapping_shr(rhs) }
                            fn wrapping_sub(self, rhs: Self) -> Self { self.wrapping_sub(rhs) }
                        })*
                    };
                }

                impl_integer_trait!(i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize);
            }
            pub mod one {
                pub trait One {
                    fn one() -> Self;
                }

                macro_rules! impl_one_integer {
                    ( $( $t:ty )* ) => {
                        $(impl One for $t {
                            fn one() -> $t { 1 }
                        })*
                    };
                }

                impl_one_integer!(i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize);

                macro_rules! impl_one_float {
                    ( $( $t:ty )* ) => {
                        $(impl One for $t {
                            fn one() -> $t { 1.0 }
                        })*
                    };
                }

                impl_one_float!(f32 f64);
            }
            pub mod signed {
                use std::ops::Neg;

                pub trait Signed: Neg<Output = Self> + std::marker::Sized {
                    fn is_negative(self) -> bool;
                    fn is_positive(self) -> bool;
                }

                macro_rules! impl_integer_trait {
                    ( $( $t:ty )* ) => {
                        $(impl Signed for $t {
                            fn is_negative(self) -> bool {
                                self.is_negative()
                            }
                            fn is_positive(self) -> bool {
                                self.is_positive()
                            }
                        })*
                    };
                }

                impl_integer_trait!(i8 i16 i32 i64 i128 isize);
            }
            pub mod zero {
                pub trait Zero {
                    fn zero() -> Self;
                }

                macro_rules! impl_zero_integer {
                    ( $( $t:ty )* ) => {
                        $(impl Zero for $t {
                            fn zero() -> $t { 0 }
                        })*
                    };
                }

                impl_zero_integer!(i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize);

                macro_rules! impl_zero_float {
                    ( $( $t:ty )* ) => {
                        $(impl Zero for $t {
                            fn zero() -> $t { 0.0 }
                        })*
                    };
                }

                impl_zero_float!(f32 f64);
            }

            pub use float::Float;
            pub use integer::Integer;
            pub use one::One;
            pub use signed::Signed;
            pub use zero::Zero;

            use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign};

            #[derive(Debug)]
            pub struct Error(pub &'static str);

            impl std::fmt::Display for Error {
                fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self.0) }
            }

            impl std::error::Error for Error {}

            pub trait UnorderedNumeric:
                Add<Self, Output = Self>
                + Sub<Self, Output = Self>
                + Mul<Self, Output = Self>
                + Div<Self, Output = Self>
                + AddAssign
                + SubAssign
                + MulAssign
                + DivAssign
                + std::fmt::Debug
                + std::fmt::Display
                + Clone
                + Copy
                + PartialEq
                + Default
                + Zero
                + One
            {
            }

            pub trait Numeric:
                Add<Self, Output = Self>
                + Sub<Self, Output = Self>
                + Mul<Self, Output = Self>
                + Div<Self, Output = Self>
                + AddAssign
                + SubAssign
                + MulAssign
                + DivAssign
                + std::fmt::Debug
                + std::fmt::Display
                + Clone
                + Copy
                + PartialEq
                + PartialOrd
                + Default
                + Zero
                + One
            {
                fn max_value() -> Self;
                fn min_value() -> Self;
            }

            pub trait IntoFloat: Numeric {
                fn as_f64(self) -> f64;
                fn as_f32(self) -> f32;
            }

            impl IntoFloat for i64 {
                fn as_f64(self) -> f64 { self as f64 }
                fn as_f32(self) -> f32 { self as f32 }
            }
        }
    }

    pub(crate) mod macros {
        pub mod iolib {
            pub use crate::{
                __cargo_equip_macro_def_iolib_read_value as read_value, __cargo_equip_macro_def_iolib_scan as scan, __cargo_equip_macro_def_iolib_scani as scani,
            };
        }

        pub mod math {}

        pub mod modint {}

        pub mod numeric {}
    }

    pub(crate) mod prelude {
        pub use crate::__cargo_equip::crates::*;
    }

    mod preludes {
        pub mod iolib {}

        pub mod math {
            pub(in crate::__cargo_equip) use crate::__cargo_equip::crates::numeric;
        }

        pub mod modint {
            pub(in crate::__cargo_equip) use crate::__cargo_equip::crates::numeric;
        }

        pub mod numeric {}
    }
}