pub struct ProconReader { reader: R, } impl ProconReader { pub fn new(reader: R) -> Self { Self { reader } } pub fn get(&mut self) -> T { use std::io::Read; let buf = self .reader .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&byte| byte == b' ' || byte == b'\n' || byte == b'\r') .take_while(|&byte| byte != b' ' && byte != b'\n' && byte != b'\r') .collect::>(); std::str::from_utf8(&buf) .unwrap() .parse() .ok() .expect("Parse Error.") } } #[allow(dead_code)] mod mint { use std::ops::{Add, BitAnd, Div, Mul, Rem, Shr, Sub}; #[derive(Copy, Clone)] pub struct Mint { x: T, mo: T, } impl Mint where T: Copy, { pub fn new(x: T, mo: T) -> Mint { Mint { x, mo } } } impl Mint where T: Copy, { pub fn val(&self) -> T { self.x } pub fn mo(&self) -> T { self.mo } } impl Add for Mint where T: Copy, T: Add, T: Rem, { type Output = Mint; fn add(self, rhs: T) -> Mint { Mint::new((self.val() + rhs % self.mo()) % self.mo(), self.mo()) } } impl Add> for Mint where T: Copy, Mint: Add>, { type Output = Mint; fn add(self, rhs: Mint) -> Mint { self + rhs.val() } } impl Sub for Mint where T: Copy, T: Add, T: Sub, T: Rem, { type Output = Mint; fn sub(self, rhs: T) -> Mint { Mint::new( (self.val() + self.mo() - rhs % self.mo()) % self.mo(), self.mo(), ) } } impl Sub> for Mint where T: Copy, Mint: Sub>, { type Output = Mint; fn sub(self, rhs: Mint) -> Mint { self - rhs.val() } } impl Mul for Mint where T: Copy, T: Mul, T: Rem, { type Output = Mint; fn mul(self, rhs: T) -> Mint { Mint::new((self.val() * rhs % self.mo()) % self.mo(), self.mo()) } } impl Mul> for Mint where T: Copy, Mint: Mul>, { type Output = Mint; fn mul(self, rhs: Mint) -> Mint { self * rhs.val() } } impl Mint where T: Copy, T: Sub, T: Div, T: PartialOrd, T: PartialEq, T: BitAnd, T: Shr, Mint: Mul>, { pub fn pow(self, y: T) -> Mint { let one = self.mo() / self.mo(); let zero = self.mo() - self.mo(); let mut res = Mint::one(self.mo()); let mut base = self; let mut exp = y; while exp > zero { if (exp & one) == one { res = res * base; } base = base * base; exp = exp >> one; } res } } impl Div for Mint where T: Copy, T: Sub, T: Div, T: PartialOrd, T: PartialEq, T: BitAnd, T: Shr, Mint: Mul>, { type Output = Mint; fn div(self, rhs: T) -> Mint { let one = self.mo() / self.mo(); self * Mint::new(rhs, self.mo()).pow(self.mo() - one - one) } } impl Div> for Mint where T: Copy, Mint: Div>, { type Output = Mint; fn div(self, rhs: Mint) -> Mint { self / rhs.val() } } impl Mint where T: Copy, T: Div, Mint: Div>, { pub fn inv(self) -> Mint { Mint::one(self.mo()) / self } } impl std::fmt::Display for Mint where T: Copy + std::fmt::Display, { fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { write!(f, "{}", self.val()) } } impl Mint where T: Copy, T: Sub, { pub fn zero(mo: T) -> Mint { Mint { x: mo - mo, mo } } } impl Mint where T: Copy, T: Div, { pub fn one(mo: T) -> Mint { Mint { x: mo / mo, mo } } } } use mint::Mint; fn main() { let stdin = std::io::stdin(); let mut rd = ProconReader::new(stdin.lock()); let n: usize = rd.get(); let m: usize = rd.get(); let x: u64 = rd.get(); let a: Vec = (0..n).map(|_| rd.get()).collect(); let b: Vec = (0..m).map(|_| rd.get()).collect(); let xa = a.iter().fold(0, |acc, x| acc ^ x); let xb = b.iter().fold(0, |acc, x| acc ^ x); if xa != xb { println!("0"); return; } let mo = 1_000_000_000 + 7; println!( "{}", Mint::new(2, mo).pow(x).pow(((n - 1) * (m - 1)) as u64) ); }