QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#259345#3082. Ascending Matrixjh05013AC ✓15ms2396kbRust16.8kb2023-11-20 20:34:132023-11-20 20:34:14

Judging History

你现在查看的是最新测评结果

  • [2023-11-20 20:34:14]
  • 评测
  • 测评结果:AC
  • 用时:15ms
  • 内存:2396kb
  • [2023-11-20 20:34:13]
  • 提交

answer

#[allow(unused_imports)] use std::{collections::*, cmp::*, ops::*};

// https://cdn.discordapp.com/attachments/1079781449621852230/1175811206091645078/SPOILER_image.png?ex=656c9685&is=655a2185&hm=5cdeb3d3a68a9dcd341c04463a941c77e127d84b7cf4b599d06fdc105047c407&
fn main() {
	let mut oj = OJ::new();
	
	let n = oj.usize();
	let m = oj.usize(); // n*m
	let k = oj.usize()-1; // k layers
	let r = oj.usize();
	let c = oj.usize();
	let v = oj.usize(); // A[r,c] = v

	// i-th start is (i+1, k-1-i)
	// i-th end is (m+i+1, n+k-1-i)
	// cell (i,j)'s upper left corner is (j, n+k-i)
	// target cell is (r+v, c+v-1)
	// target cell's upper left corner is (c+v-2, n+k+2-r-v)
	let targ_x = c+v-2;
	let targ_y = n+k+2-r-v;

	let mf = Modfact::new(1000);
	let mut mat_x = SquareMatrix::<Modint>::new(k);
	let mut mat_1 = SquareMatrix::<Modint>::new(k);
	for i in 0..k {
		let xstart = i+1;
		let ystart = k-1-i;
		for j in 0..k {
			let xend = m+j+1;
			let yend = n+k-1-j;
			if xstart > xend || ystart > yend { continue; }
			// cross the target diagonal (x+y = targ_x+targ_y) at y
			for y in ystart..=yend {
				if targ_x + targ_y < y { continue; }
				let x = targ_x + targ_y - y;
				if !(xstart..=xend).contains(&x) { continue; }

				// count ways
				let w = x - xstart; let h = y - ystart;
				let ways1 = mf.comb(w+h, w);
				let w = xend - x; let h = yend - y;
				let ways2 = mf.comb(w+h, w);
				let ways = ways1 * ways2;

				// add to appropriate matrix
				if y >= targ_y { mat_x[i][j] += ways; }
				else if y+1 == targ_y { }
				else { mat_1[i][j] += ways; }
			}
		}
	}

	let poly = SquareMatrix::det_axb(&mut mat_x, &mut mat_1);
	oj.write(poly.get(v-1).unwrap_or(&modint(0)));
}

///////////////////////////////////////

pub mod square_matrix_mod {
	use std::{ops::*, fmt::*, mem::take};

	pub trait Semiring:
		Neg<Output=Self>
		+ AddAssign + Add<Output=Self> + MulAssign + Mul<Output=Self>
		+ Clone + Default + From<i32> + PartialEq + Display + Debug {}
	impl<T> Semiring for T where T:
		Neg<Output=Self>
		+ AddAssign + Add<Output=Self> + MulAssign + Mul<Output=Self>
		+ Clone + Default + From<i32> + PartialEq + Display + Debug {}

	/// A square matrix.
	#[derive(Debug, Clone, Eq, PartialEq, Default)]
	pub struct SquareMatrix<T> { pub mat: Vec<Vec<T>> }

	impl<T> SquareMatrix<T> {
		/// Creates an empty `n * n` matrix.
		pub fn new(n: usize) -> Self where T: Clone + Default {
			Self { mat: vec![vec![T::default(); n]; n] }
		}
		/// Cretaes a matrix out of `n * n` values.
		pub fn from_line(n: usize, vals: &[T]) -> Self where T: Clone {
			assert!(vals.len() == n*n);
			if n == 0 { return Self { mat: vec![] }; }
			Self { mat: vals.chunks(n).map(<[T]>::to_vec).collect() }
		}
		/// Creates an identity `n * n` matrix.
		pub fn eye(n: usize) -> Self where T: Clone + Default + From<i32> {
			let mut mat = Self::new(n);
			for i in 0..n { mat[i][i] = 1.into(); }
			mat
		}

		/// Returns `n`.
		pub fn n(&self) -> usize { self.mat.len() }

		/// Iterates over its elements.
		pub fn elements(&self) -> impl Iterator<Item = &T> {
			self.mat.iter().flat_map(|row| row.iter())
		}
		/// Iterates over its owned elements.
		pub fn into_elements(self) -> impl Iterator<Item = T> {
			self.mat.into_iter().flat_map(IntoIterator::into_iter)
		}
		/// Iterates mutably over its elements.
		pub fn elements_mut(&mut self) -> impl Iterator<Item = &mut T> {
			self.mat.iter_mut().flat_map(|row| row.iter_mut())
		}
	}

	// io
	impl<T: Display> Display for SquareMatrix<T> {
		fn fmt(&self, f: &mut Formatter) -> Result {
			for row in &self.mat {
				for x in row { write!(f, "{} ", x)?; }
				writeln!(f)?;
			}
			Ok(())
		}
	}

	// indexing
	/// Returns the `i`-th row.
	impl<T> Index<usize> for SquareMatrix<T> { type Output = [T];
		fn index(&self, i: usize) -> &Self::Output { &self.mat[i] }
	}
	/// Returns the `i`-th row mutably.
	impl<T> IndexMut<usize> for SquareMatrix<T> {
		fn index_mut(&mut self, i: usize) -> &mut Self::Output { &mut self.mat[i] }
	}

	// arithmetic
	impl<T: Neg<Output = T> + Default> Neg for SquareMatrix<T> {
		type Output = Self;
		fn neg(mut self) -> Self::Output {
			self.elements_mut().for_each(|x| *x = -take(x));
			self
		}
	}
	impl<T: AddAssign> AddAssign for SquareMatrix<T> {
		fn add_assign(&mut self, b: Self) {
			assert_eq!(self.n(), b.n(), "Matrix sizes mismatch");
			self.elements_mut().zip(b.into_elements()).for_each(|(x, y)| *x += y);
		}
	}
	impl<T: Add<Output = T> + Default> Add for SquareMatrix<T> { type Output = Self;
		fn add(mut self, b: Self) -> Self {
			assert_eq!(self.n(), b.n(), "Matrix sizes mismatch");
			self.elements_mut().zip(b.into_elements())
				.for_each(|(x, y)| *x = take(x) + y);
			self
		}
	}
	impl<T: SubAssign> SubAssign for SquareMatrix<T> {
		fn sub_assign(&mut self, b: Self) {
			assert_eq!(self.n(), b.n(), "Matrix sizes mismatch");
			self.elements_mut().zip(b.into_elements()).for_each(|(x, y)| *x -= y);
		}
	}
	impl<T: Sub<Output = T> + Default> Sub for SquareMatrix<T> { type Output = Self;
		fn sub(mut self, b: Self) -> Self {
			assert_eq!(self.n(), b.n(), "Matrix sizes mismatch");
			self.elements_mut().zip(b.into_elements())
				.for_each(|(x, y)| *x = take(x) - y);
			self
		}
	}
	impl<T: MulAssign + Clone> MulAssign<T> for SquareMatrix<T> {
		fn mul_assign(&mut self, k: T) {
			self.elements_mut().for_each(|x| *x *= k.clone());
		}
	}
	impl<T: Mul<Output = T> + Default + Clone> Mul<T> for SquareMatrix<T> {
		type Output = Self;
		fn mul(mut self, k: T) -> Self {
			self.elements_mut().for_each(|x| *x = take(x) * k.clone());
			self
		}
	}
	impl<T: Semiring> MulAssign for SquareMatrix<T> {
		fn mul_assign(&mut self, b: Self) { *self = take(self) * b; }
	}
	impl<T: Semiring> Mul for SquareMatrix<T> {
		type Output = Self;
		fn mul(self, b: Self) -> Self {
			assert_eq!(self.n(), b.n(), "Matrix sizes mismatch");
			let mut ans = Self::new(self.n());
			for (j, bj) in b.mat.iter().enumerate() {
			for (ai, si) in ans.mat.iter_mut().zip(self.mat.iter()) {
			for (aik, bjk) in ai.iter_mut().zip(bj.iter()) {
				unsafe { *aik += si.get_unchecked(j).clone() * bjk.clone(); }
			}}}
			ans
		}
	}
	impl<T: Semiring> SquareMatrix<T> {
		/// Returns its `k`-th power.
		pub fn pow(&self, mut k: u64) -> Self {
			let mut ans = Self::eye(self.n());
			let mut a = self.clone();
			while k != 0 {
				if k&1 == 1 { ans*= a.clone(); }
				k>>= 1; a*= a.clone();
			}
			ans
		}
	}
} pub use square_matrix_mod::SquareMatrix;

pub mod gauss_elim_mod {
	use std::ops::Div;
	use super::square_matrix_mod::{Semiring, *};

	pub trait Field: Semiring + Div<Output=Self> {}
	impl<T> Field for T where T: Semiring + Div<Output=Self> {}

	impl<T> SquareMatrix<T> where T: Semiring {
		pub fn swap_row(&mut self, i: usize, j: usize) -> bool {
			if i == j { false }
			else { self.mat.swap(i, j); true }
		}
		pub fn swap_col(&mut self, i: usize, j: usize) -> bool {
			if i == j { false }
			else { for row in &mut self.mat { row.swap(i, j); } true }
		}
		pub fn mul_row(&mut self, i: usize, k: T) {
			for x in &mut self[i] { *x *= k.clone(); }
		}
		pub fn mul_col(&mut self, j: usize, k: T) {
			for row in &mut self.mat { row[j] *= k.clone(); }
		}
		pub fn add_row(&mut self, fr: usize, k: T, to: usize) {
			assert_ne!(fr, to, "Bad row-add");
			let row = std::mem::take(&mut self.mat[fr]);
			for (x, y) in self.mat[to].iter_mut().zip(row.iter()) {
				*x += k.clone() * y.clone();
			}
			self.mat[fr] = row;
		}
		pub fn add_col(&mut self, fr: usize, k: T, to: usize) {
			assert_ne!(fr, to, "Bad col-add");
			for row in &mut self.mat {
				let v = row[fr].clone();
				row[to] += k.clone() * v;
			}
		}
	}

	impl<T: Field> SquareMatrix<T> {
		pub fn make_ref(&mut self) -> T {
			let n = self.n();
			let mut istart = 0;
			let mut det: T = 1.into();
			for j in 0..n {
				// Find and swap pivot
				let mut piv = istart;
				while piv < n && self[piv][j] == T::default() { piv += 1; }
				if piv == n { continue; }
				if istart != piv {
					det = -det; self.swap_row(istart, piv);
				}
				// Zero the other rows
				let v = self.mat[istart][j].clone();
				det *= v.clone();
				self.mul_row(istart, T::from(1) / v);
				for i in istart+1..n {
					let v = self.mat[i][j].clone();
					self.add_row(istart, -v, i);
				}
				istart += 1;
			}
			for i in 0..n { det *= self.mat[i][i].clone(); }
			det
		}
	}
}

pub mod char_poly_mod {
	use super::SquareMatrix;
	use super::gauss_elim_mod::Field;

	impl<T: Field> SquareMatrix<T> {
		/// Transforms it into upper Hessenberg form.
		pub fn make_hessenberg(&mut self) {
			let n = self.n();
			for piv in 1..n {
				// find pivot and swap
				let mut i = piv;
				while i < n {
					if self[i][piv-1] != T::default() { break; }
					i += 1;
				}
				if i == n { continue; }
				self.swap_row(i, piv); self.swap_col(i, piv);
				// zero other rows
				let x = T::from(1) / self[piv][piv-1].clone();
				for i in i+1..n {
					let mul = self[i][piv-1].clone() * x.clone();
					self.add_row(piv, -mul.clone(), i);
					self.add_col(i, mul, piv);
				}
			}
		}

		/// Transforms it into upper Hessenberg form and returns det(xI + A).
		pub fn make_hessenberg_det_xia(&mut self) -> Vec<T> {
			self.make_hessenberg();
			let mut dets = vec![vec![T::from(1)]];
			let mut det = vec![T::from(1)];
			let n = self.n();
			for k in 0..n {
				let mut q = vec![T::default()];
				q.append(&mut det.clone());
				for (x, y) in q.iter_mut().zip(det.iter()) {
					*x += self[k][k].clone() * y.clone();
				}
				det = q;
				let mut prod = T::from(1);
				for i in (0..k).rev() {
					prod *= -self[i+1][i].clone();
					let z = self[i][k].clone() * prod.clone();
					let add = &dets[i];
					for (x, y) in det.iter_mut().zip(add.iter()) {
						*x += y.clone() * z.clone();
					}
				}
				dets.push(det.clone());
			}
			det
		}

		/// Returns det(Ax + B).
		// https://tistory.joonhyung.xyz/19
		pub fn det_axb(a: &mut Self, b: &mut Self) -> Vec<T> {
			let n = a.n();
			assert_eq!(n, b.n(), "Matrix sizes mismatch");

			let (mut alpha, mut beta) = (0, 0);
			let mut det = T::from(1);
			while alpha + beta < n {
				for i in 0..alpha {
					b.add_col(i, -a[i][alpha].clone(), alpha);
					a.add_col(i, -a[i][alpha].clone(), alpha);
				}
				for i in alpha..n-beta {
					if a[i][alpha] != T::default() {
						if a.swap_row(alpha, i) { det = -det; }
						b.swap_row(alpha, i);
						break;
					}
				}
				if a[alpha][alpha] != T::default() {
					det *= a[alpha][alpha].clone();
					let v = T::from(1) / a[alpha][alpha].clone();
					a.mul_row(alpha, v.clone()); b.mul_row(alpha, v);
					for i in alpha+1..n {
						b.add_row(alpha, -a[i][alpha].clone(), i);
						a.add_row(alpha, -a[i][alpha].clone(), i);
					}
					alpha += 1;
				}
				else {
					let r = n-1-beta;
					if a.swap_col(alpha, r) { det = -det; }
					b.swap_col(alpha, r);
					let mut pos = None;
					for i in (0..=r).rev() {
						if b[i][r] != T::default() { pos = Some(i); break; }
					}

					let Some(pos) = pos else { return vec![]; };
					if pos < alpha {
						a.swap_row(pos, alpha-1); b.swap_row(pos, alpha-1);
						a.swap_col(pos, alpha-1); b.swap_col(pos, alpha-1);
						if a.swap_row(alpha-1, r) { det = -det; }
						b.swap_row(alpha-1, r);
						alpha -= 1;
					}
					else {
						if a.swap_row(pos, r) { det = -det; }
						b.swap_row(pos, r);
					}
					det *= b[r][r].clone();
					let v = T::from(1) / b[r][r].clone();
					a.mul_row(r, v.clone()); b.mul_row(r, v);
					for i in 0..r {
						a.add_row(r, -b[i][r].clone(), i);
						b.add_row(r, -b[i][r].clone(), i);
					}
					beta += 1;
				}
			}

			let mut c = SquareMatrix::new(alpha);
			for i in 0..alpha { for j in 0..alpha {
				c[i][j] = b[i][j].clone();
			}}
			let mut poly = c.make_hessenberg_det_xia();
			poly.iter_mut().for_each(|x| *x *= det.clone());
			poly
		}
	}
}

pub mod modint_998244353 {
	pub const MOD: i32 = 998244353;
	pub const MODL: i64 = MOD as i64;
	
	use std::ops::*;
	use std::fmt::*;
	
	#[derive(Default, Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
	pub struct Modint { v: i32 }
	pub fn modint(v: i64) -> Modint { Modint::new(v) }
	
	impl Modint {
		pub fn new(v: i64) -> Modint { Self { v: v.rem_euclid(MODL) as i32 } }
	
		pub fn pow(&self, mut n: u64) -> Self {
			let mut ans = Modint::new(1);
			let mut a = *self;
			while n != 0 {
				if n&1 == 1 { ans*= a; }
				n>>= 1; a*= a;
			}
			ans
		}
	
		pub fn inv(&self) -> Self {
			assert!(self.v != 0, "Cannot invert 0");
			self.pow((MOD-2) as u64)
		}
	}
	
	// io
	impl std::str::FromStr for Modint {
		type Err = std::num::ParseIntError;
		fn from_str(s: &str) -> std::result::Result<Self, Self::Err> {
			Ok(Self::new(s.parse::<i64>()?))
		}
	}
	impl Display for Modint {
		fn fmt(&self, f: &mut Formatter) -> Result { write!(f, "{}", self.v) }
	}
	impl From<Modint> for i32 {
		fn from(num: Modint) -> i32 { num.v }
	}
	impl From<i32> for Modint {
		fn from(num: i32) -> Modint { Modint::new(num as i64) }
	}
	
	// arithmetic
	impl AddAssign for Modint {
		fn add_assign(&mut self, b: Self) {
			self.v+= b.v; if self.v >= MOD { self.v-= MOD; }
		}
	}
	impl Add for Modint { type Output = Self;
		fn add(self, b: Self) -> Self { let mut z = self; z+= b; z }
	}
	impl Neg for Modint { type Output = Self;
		fn neg(self) -> Self { Self::default() - self }
	}
	impl SubAssign for Modint {
		fn sub_assign(&mut self, b: Self) {
			self.v-= b.v; if self.v < 0 { self.v+= MOD; }
		}
	}
	impl Sub for Modint { type Output = Self;
		fn sub(self, b: Self) -> Self { let mut z = self; z-= b; z }
	}
	impl MulAssign for Modint {
		fn mul_assign(&mut self, b: Self) {
			self.v = ((self.v as i64) * (b.v as i64) % MODL) as i32;
		}
	}
	impl Mul for Modint { type Output = Self;
		fn mul(self, b: Self) -> Self { let mut z = self; z*= b; z }
	}
	impl DivAssign for Modint {
		fn div_assign(&mut self, b: Self) { *self = *self / b; }
	}
	#[allow(clippy::suspicious_arithmetic_impl)]
	impl Div for Modint { type Output = Self;
		fn div(self, b: Self) -> Self { self * b.inv() }
	}
	
	// factorial
	#[derive(Clone, Debug, Default)]
	pub struct Modfact {
		pub fact: Vec<Modint>,
		pub ifact: Vec<Modint>,
	}
	
	impl Modfact {
		pub fn new(n: usize) -> Self {
			let mut fact = vec![modint(1)];
			for i in 1..=n {
				fact.push(fact[i-1] * modint(i as i64));
			}
			let mut ifact = vec![fact[n].inv(); n+1];
			for i in (0..n).rev() {
				ifact[i] = ifact[i+1] * modint((i+1) as i64);
			}
			Self { fact, ifact }
		}
		pub fn len(&self) -> usize { self.fact.len() }
	
		pub fn comb(&self, n: usize, r: usize) -> Modint {
			assert!(r <= n && n < self.len(),
				"Bad comb-query values ({}, {})", n, r
			);
			self.fact[n] * self.ifact[r] * self.ifact[n-r]
		}
	}	
}
pub use modint_998244353::{MOD, MODL, Modint, Modfact, modint};


pub mod oj_default_mod {
	use std::{fmt::{Display, Debug}, io::*, process::*, str::*};

	pub struct OJ {
		buffer: std::str::SplitWhitespace<'static>,
		out: BufWriter<Stdout>
	}
	
	impl OJ {
		#[allow(clippy::new_without_default)]
		pub fn new() -> Self {
			let mut inp = String::new();
			stdin().read_to_string(&mut inp).unwrap();
			let input = Box::leak(inp.into_boxed_str()).split_whitespace();
			Self { buffer: input, out: BufWriter::new(stdout()) }
		}
	
		pub fn try_read<T: FromStr>(&mut self) -> std::result::Result<T, &str> {
			self.buffer.next().ok_or("EOF")?
				.parse().or(Err("Failed parse"))
		}
		pub fn read<T: FromStr>(&mut self) -> T { self.try_read().unwrap() }
		pub fn i32(&mut self) -> i32 { self.read() }
		pub fn i64(&mut self) -> i64 { self.read() }
		pub fn u32(&mut self) -> u32 { self.read() }
		pub fn u64(&mut self) -> u64 { self.read() }
		pub fn usize(&mut self) -> usize { self.read() }
		pub fn f64(&mut self) -> f64 { self.read() }
		pub fn string(&mut self) -> String { self.read() }

		pub fn read_vec<T: FromStr>(&mut self, n: usize) -> Vec<T>
			{ (0..n).map(|_| self.read()).collect() }
		pub fn read_grid<T: FromStr>(&mut self, n: usize, m: usize) -> Vec<Vec<T>>
			{ (0..n).map(|_| self.read_vec(m)).collect() }

		pub fn write<T: Display>(&mut self, v: T) -> &mut Self
			{ write!(self.out, "{v}").unwrap(); self }
		pub fn writes<T: Display>(&mut self, vals: &[T]) -> &mut Self
			{ for v in vals { self.write(v).sp(); } self }
		pub fn debug<T: Debug>(&mut self, v: T) -> &mut Self
			{ write!(self.out, "{v:?}").unwrap(); self }
		pub fn sp(&mut self) -> &mut Self { self.write(' ') }
		pub fn ln(&mut self) -> &mut Self { self.write('\n') }
		pub fn quit<T: Display>(&mut self, v: T) -> !
			{ self.write(v); self.out.flush().unwrap(); exit(0) }
	}
}
pub use oj_default_mod::OJ;


詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 2112kb

input:

148 129 48 144 105 13

output:

467058311

result:

ok single line: '467058311'

Test #2:

score: 0
Accepted
time: 0ms
memory: 2032kb

input:

57 48 11 56 9 1

output:

951177245

result:

ok single line: '951177245'

Test #3:

score: 0
Accepted
time: 6ms
memory: 2212kb

input:

121 146 72 117 72 25

output:

284798523

result:

ok single line: '284798523'

Test #4:

score: 0
Accepted
time: 0ms
memory: 2316kb

input:

66 142 11 51 124 4

output:

542285716

result:

ok single line: '542285716'

Test #5:

score: 0
Accepted
time: 8ms
memory: 2256kb

input:

45 127 98 3 31 80

output:

116902187

result:

ok single line: '116902187'

Test #6:

score: 0
Accepted
time: 3ms
memory: 2172kb

input:

125 199 45 51 91 21

output:

715355617

result:

ok single line: '715355617'

Test #7:

score: 0
Accepted
time: 0ms
memory: 2232kb

input:

41 153 6 6 147 2

output:

190519561

result:

ok single line: '190519561'

Test #8:

score: 0
Accepted
time: 2ms
memory: 2396kb

input:

112 108 69 99 29 47

output:

481688971

result:

ok single line: '481688971'

Test #9:

score: 0
Accepted
time: 11ms
memory: 2396kb

input:

138 99 94 73 43 73

output:

667469005

result:

ok single line: '667469005'

Test #10:

score: 0
Accepted
time: 0ms
memory: 1984kb

input:

143 147 18 24 141 9

output:

763965115

result:

ok single line: '763965115'

Test #11:

score: 0
Accepted
time: 8ms
memory: 2256kb

input:

99 63 97 78 51 66

output:

130195301

result:

ok single line: '130195301'

Test #12:

score: 0
Accepted
time: 0ms
memory: 2192kb

input:

103 23 10 25 7 4

output:

674555733

result:

ok single line: '674555733'

Test #13:

score: 0
Accepted
time: 2ms
memory: 2004kb

input:

137 194 42 125 104 17

output:

416667361

result:

ok single line: '416667361'

Test #14:

score: 0
Accepted
time: 1ms
memory: 2252kb

input:

191 13 37 42 2 21

output:

530754407

result:

ok single line: '530754407'

Test #15:

score: 0
Accepted
time: 2ms
memory: 2084kb

input:

195 33 53 101 29 32

output:

851306824

result:

ok single line: '851306824'

Test #16:

score: 0
Accepted
time: 0ms
memory: 2040kb

input:

84 173 8 70 70 6

output:

25135799

result:

ok single line: '25135799'

Test #17:

score: 0
Accepted
time: 1ms
memory: 2092kb

input:

39 53 49 37 6 9

output:

640044940

result:

ok single line: '640044940'

Test #18:

score: 0
Accepted
time: 5ms
memory: 2116kb

input:

135 129 68 134 86 16

output:

910022919

result:

ok single line: '910022919'

Test #19:

score: 0
Accepted
time: 2ms
memory: 2248kb

input:

62 74 56 28 12 46

output:

774987233

result:

ok single line: '774987233'

Test #20:

score: 0
Accepted
time: 8ms
memory: 2300kb

input:

87 135 81 27 44 58

output:

629485683

result:

ok single line: '629485683'

Test #21:

score: 0
Accepted
time: 3ms
memory: 2148kb

input:

148 199 44 79 81 40

output:

369408819

result:

ok single line: '369408819'

Test #22:

score: 0
Accepted
time: 0ms
memory: 2192kb

input:

18 195 5 17 151 5

output:

198068951

result:

ok single line: '198068951'

Test #23:

score: 0
Accepted
time: 9ms
memory: 2160kb

input:

200 137 75 67 65 74

output:

864017958

result:

ok single line: '864017958'

Test #24:

score: 0
Accepted
time: 5ms
memory: 2140kb

input:

171 162 56 113 97 30

output:

255341800

result:

ok single line: '255341800'

Test #25:

score: 0
Accepted
time: 0ms
memory: 2116kb

input:

8 134 38 1 93 10

output:

282048962

result:

ok single line: '282048962'

Test #26:

score: 0
Accepted
time: 2ms
memory: 2340kb

input:

13 55 93 3 25 40

output:

852404927

result:

ok single line: '852404927'

Test #27:

score: 0
Accepted
time: 0ms
memory: 2144kb

input:

169 157 42 77 108 39

output:

595819517

result:

ok single line: '595819517'

Test #28:

score: 0
Accepted
time: 6ms
memory: 2200kb

input:

41 199 87 18 82 58

output:

698977796

result:

ok single line: '698977796'

Test #29:

score: 0
Accepted
time: 3ms
memory: 2176kb

input:

190 68 57 188 59 15

output:

46174623

result:

ok single line: '46174623'

Test #30:

score: 0
Accepted
time: 4ms
memory: 2184kb

input:

90 52 71 39 41 23

output:

417181087

result:

ok single line: '417181087'

Test #31:

score: 0
Accepted
time: 8ms
memory: 2168kb

input:

108 76 89 55 40 13

output:

210578964

result:

ok single line: '210578964'

Test #32:

score: 0
Accepted
time: 1ms
memory: 2148kb

input:

166 191 27 102 30 11

output:

365224233

result:

ok single line: '365224233'

Test #33:

score: 0
Accepted
time: 0ms
memory: 2120kb

input:

41 166 4 10 49 2

output:

245797147

result:

ok single line: '245797147'

Test #34:

score: 0
Accepted
time: 7ms
memory: 2148kb

input:

135 128 79 44 16 6

output:

203896980

result:

ok single line: '203896980'

Test #35:

score: 0
Accepted
time: 8ms
memory: 2236kb

input:

101 193 79 43 65 75

output:

27637457

result:

ok single line: '27637457'

Test #36:

score: 0
Accepted
time: 2ms
memory: 2124kb

input:

88 81 53 35 54 47

output:

950708598

result:

ok single line: '950708598'

Test #37:

score: 0
Accepted
time: 1ms
memory: 2144kb

input:

87 40 28 37 8 8

output:

817953396

result:

ok single line: '817953396'

Test #38:

score: 0
Accepted
time: 9ms
memory: 2120kb

input:

193 136 94 12 94 23

output:

145619900

result:

ok single line: '145619900'

Test #39:

score: 0
Accepted
time: 3ms
memory: 2156kb

input:

90 183 67 8 171 26

output:

899333159

result:

ok single line: '899333159'

Test #40:

score: 0
Accepted
time: 1ms
memory: 2120kb

input:

107 178 32 24 103 12

output:

82019799

result:

ok single line: '82019799'

Test #41:

score: 0
Accepted
time: 2ms
memory: 2076kb

input:

160 23 61 60 17 3

output:

350971684

result:

ok single line: '350971684'

Test #42:

score: 0
Accepted
time: 0ms
memory: 2092kb

input:

100 176 10 54 58 4

output:

978823166

result:

ok single line: '978823166'

Test #43:

score: 0
Accepted
time: 0ms
memory: 2220kb

input:

181 183 42 7 91 41

output:

690262327

result:

ok single line: '690262327'

Test #44:

score: 0
Accepted
time: 3ms
memory: 2124kb

input:

105 131 47 53 68 33

output:

806603020

result:

ok single line: '806603020'

Test #45:

score: 0
Accepted
time: 5ms
memory: 2216kb

input:

51 10 100 1 5 73

output:

341852925

result:

ok single line: '341852925'

Test #46:

score: 0
Accepted
time: 6ms
memory: 2168kb

input:

87 198 73 75 109 72

output:

741170008

result:

ok single line: '741170008'

Test #47:

score: 0
Accepted
time: 0ms
memory: 2136kb

input:

25 158 13 22 1 1

output:

237363061

result:

ok single line: '237363061'

Test #48:

score: 0
Accepted
time: 3ms
memory: 2084kb

input:

64 112 71 28 109 10

output:

350168232

result:

ok single line: '350168232'

Test #49:

score: 0
Accepted
time: 3ms
memory: 2276kb

input:

143 191 52 10 98 10

output:

71885894

result:

ok single line: '71885894'

Test #50:

score: 0
Accepted
time: 1ms
memory: 2140kb

input:

30 130 36 22 85 6

output:

909971212

result:

ok single line: '909971212'

Test #51:

score: 0
Accepted
time: 1ms
memory: 2088kb

input:

154 136 38 34 109 15

output:

655764791

result:

ok single line: '655764791'

Test #52:

score: 0
Accepted
time: 0ms
memory: 2124kb

input:

13 112 7 9 55 1

output:

623849663

result:

ok single line: '623849663'

Test #53:

score: 0
Accepted
time: 2ms
memory: 2348kb

input:

137 103 47 56 77 35

output:

43033659

result:

ok single line: '43033659'

Test #54:

score: 0
Accepted
time: 0ms
memory: 2056kb

input:

40 17 37 11 7 15

output:

803046927

result:

ok single line: '803046927'

Test #55:

score: 0
Accepted
time: 0ms
memory: 2268kb

input:

166 14 58 49 1 26

output:

664593299

result:

ok single line: '664593299'

Test #56:

score: 0
Accepted
time: 0ms
memory: 2096kb

input:

88 195 15 10 120 5

output:

925522664

result:

ok single line: '925522664'

Test #57:

score: 0
Accepted
time: 15ms
memory: 2220kb

input:

164 166 96 161 138 32

output:

111053370

result:

ok single line: '111053370'

Test #58:

score: 0
Accepted
time: 13ms
memory: 2232kb

input:

145 135 94 68 83 9

output:

394110532

result:

ok single line: '394110532'

Test #59:

score: 0
Accepted
time: 5ms
memory: 2184kb

input:

154 173 63 5 77 51

output:

540440686

result:

ok single line: '540440686'

Test #60:

score: 0
Accepted
time: 0ms
memory: 2216kb

input:

20 91 30 20 83 17

output:

961395776

result:

ok single line: '961395776'

Test #61:

score: 0
Accepted
time: 0ms
memory: 2152kb

input:

144 39 13 77 9 5

output:

99731481

result:

ok single line: '99731481'

Test #62:

score: 0
Accepted
time: 8ms
memory: 2276kb

input:

87 152 83 4 59 81

output:

139490896

result:

ok single line: '139490896'

Test #63:

score: 0
Accepted
time: 13ms
memory: 2156kb

input:

171 135 89 114 124 10

output:

736020363

result:

ok single line: '736020363'

Test #64:

score: 0
Accepted
time: 4ms
memory: 2276kb

input:

82 41 99 66 6 5

output:

882042301

result:

ok single line: '882042301'

Test #65:

score: 0
Accepted
time: 0ms
memory: 2124kb

input:

33 114 28 11 73 11

output:

653378940

result:

ok single line: '653378940'

Test #66:

score: 0
Accepted
time: 0ms
memory: 2120kb

input:

180 73 10 43 63 9

output:

170492767

result:

ok single line: '170492767'

Test #67:

score: 0
Accepted
time: 2ms
memory: 2160kb

input:

33 185 63 19 107 7

output:

907253908

result:

ok single line: '907253908'

Test #68:

score: 0
Accepted
time: 0ms
memory: 2116kb

input:

69 90 22 34 31 3

output:

137223161

result:

ok single line: '137223161'

Test #69:

score: 0
Accepted
time: 0ms
memory: 2092kb

input:

42 45 60 29 38 36

output:

99908563

result:

ok single line: '99908563'

Test #70:

score: 0
Accepted
time: 1ms
memory: 2128kb

input:

69 158 34 56 39 17

output:

681472254

result:

ok single line: '681472254'

Test #71:

score: 0
Accepted
time: 5ms
memory: 2112kb

input:

66 69 84 5 8 41

output:

277373736

result:

ok single line: '277373736'

Test #72:

score: 0
Accepted
time: 3ms
memory: 2152kb

input:

168 31 68 66 4 21

output:

528816013

result:

ok single line: '528816013'

Test #73:

score: 0
Accepted
time: 4ms
memory: 2228kb

input:

65 33 94 2 30 76

output:

331224077

result:

ok single line: '331224077'

Test #74:

score: 0
Accepted
time: 0ms
memory: 2040kb

input:

84 111 12 28 106 12

output:

95279945

result:

ok single line: '95279945'

Test #75:

score: 0
Accepted
time: 6ms
memory: 2236kb

input:

102 77 83 95 62 51

output:

773914979

result:

ok single line: '773914979'

Test #76:

score: 0
Accepted
time: 7ms
memory: 2172kb

input:

113 144 76 24 68 13

output:

845242590

result:

ok single line: '845242590'

Test #77:

score: 0
Accepted
time: 0ms
memory: 2124kb

input:

45 24 9 10 2 5

output:

71790514

result:

ok single line: '71790514'

Test #78:

score: 0
Accepted
time: 5ms
memory: 2168kb

input:

158 98 61 86 50 29

output:

123475901

result:

ok single line: '123475901'

Test #79:

score: 0
Accepted
time: 1ms
memory: 2036kb

input:

118 52 27 11 23 21

output:

489202572

result:

ok single line: '489202572'

Test #80:

score: 0
Accepted
time: 1ms
memory: 2256kb

input:

122 148 35 112 17 17

output:

856169627

result:

ok single line: '856169627'

Test #81:

score: 0
Accepted
time: 0ms
memory: 2108kb

input:

135 114 15 20 43 9

output:

873320383

result:

ok single line: '873320383'

Test #82:

score: 0
Accepted
time: 5ms
memory: 2180kb

input:

89 70 84 70 12 18

output:

302990320

result:

ok single line: '302990320'

Test #83:

score: 0
Accepted
time: 2ms
memory: 2264kb

input:

15 68 67 5 51 66

output:

980298686

result:

ok single line: '980298686'

Test #84:

score: 0
Accepted
time: 1ms
memory: 2244kb

input:

50 2 73 40 2 8

output:

550497760

result:

ok single line: '550497760'

Test #85:

score: 0
Accepted
time: 5ms
memory: 2268kb

input:

117 88 83 93 1 50

output:

645491986

result:

ok single line: '645491986'

Test #86:

score: 0
Accepted
time: 2ms
memory: 2104kb

input:

45 173 54 34 93 3

output:

330947509

result:

ok single line: '330947509'

Test #87:

score: 0
Accepted
time: 0ms
memory: 2132kb

input:

39 10 22 34 6 20

output:

184357429

result:

ok single line: '184357429'

Test #88:

score: 0
Accepted
time: 2ms
memory: 2180kb

input:

58 27 71 55 19 22

output:

201813851

result:

ok single line: '201813851'

Test #89:

score: 0
Accepted
time: 1ms
memory: 2120kb

input:

123 57 40 14 38 23

output:

891805630

result:

ok single line: '891805630'

Test #90:

score: 0
Accepted
time: 0ms
memory: 2172kb

input:

84 64 70 12 2 23

output:

351372969

result:

ok single line: '351372969'

Test #91:

score: 0
Accepted
time: 3ms
memory: 2244kb

input:

46 160 72 21 146 9

output:

625614461

result:

ok single line: '625614461'

Test #92:

score: 0
Accepted
time: 2ms
memory: 2160kb

input:

45 99 57 25 40 4

output:

498175745

result:

ok single line: '498175745'

Test #93:

score: 0
Accepted
time: 0ms
memory: 1996kb

input:

15 21 12 14 6 3

output:

727195216

result:

ok single line: '727195216'

Test #94:

score: 0
Accepted
time: 1ms
memory: 2060kb

input:

154 77 32 73 62 15

output:

513610382

result:

ok single line: '513610382'

Test #95:

score: 0
Accepted
time: 0ms
memory: 2128kb

input:

165 97 16 158 69 11

output:

308621770

result:

ok single line: '308621770'

Test #96:

score: 0
Accepted
time: 8ms
memory: 2180kb

input:

146 128 97 132 24 10

output:

751957330

result:

ok single line: '751957330'

Test #97:

score: 0
Accepted
time: 1ms
memory: 2152kb

input:

49 39 35 2 10 14

output:

338882448

result:

ok single line: '338882448'

Test #98:

score: 0
Accepted
time: 2ms
memory: 2140kb

input:

73 1 73 35 1 44

output:

126891463

result:

ok single line: '126891463'

Test #99:

score: 0
Accepted
time: 1ms
memory: 2224kb

input:

69 82 59 1 73 1

output:

436743471

result:

ok single line: '436743471'

Test #100:

score: 0
Accepted
time: 1ms
memory: 2124kb

input:

88 86 40 19 77 4

output:

758000538

result:

ok single line: '758000538'