/*------------------------------------------------------------------*/ /*------------------------- begin template -------------------------*/ /*------------------------------------------------------------------*/ // ref: tanakh // diff: using Parser macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut parser = Parser::from_str($s); input_inner!{parser, $($r)*} }; (parser = $parser:ident, $($r:tt)*) => { input_inner!{$parser, $($r)*} }; (new_stdin_parser = $parser:ident, $($r:tt)*) => { let stdin = std::io::stdin(); let reader = std::io::BufReader::new(stdin.lock()); let mut $parser = Parser::new(reader); input_inner!{$parser, $($r)*} }; ($($r:tt)*) => { input!{new_stdin_parser = parser, $($r)*} }; } macro_rules! input_inner { ($parser:ident) => {}; ($parser:ident, ) => {}; ($parser:ident, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($parser, $t); input_inner!{$parser $($r)*} }; } macro_rules! read_value { ($parser:ident, ( $($t:tt),* )) => { ( $(read_value!($parser, $t)),* ) }; ($parser:ident, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($parser, $t)).collect::>() }; ($parser:ident, chars) => { read_value!($parser, String).chars().collect::>() }; ($parser:ident, char_) => { read_value!($parser, String).chars().collect::>()[0] }; ($parser:ident, usize1) => { read_value!($parser, usize) - 1 }; ($parser:ident, i64_) => { $parser.fast_i64() }; ($parser:ident, usize_) => { $parser.fast_i64() as usize }; ($parser:ident, usize1_) => { ($parser.fast_i64() - 1) as usize }; ($parser:ident, $t:ty) => { $parser.next::<$t>().expect("Parse error") }; } use std::io; use std::io::BufRead; use std::str; // ref: tatsuya6502 // ref: wariuni // diff: using std::io::BufRead::fill_buf() pub struct Parser { pub reader: R, buf: Vec, pos: usize, } impl Parser { pub fn from_str(s: &str) -> Parser { Parser { reader: io::empty(), buf: s.as_bytes().to_vec(), pos: 0, } } } impl Parser { pub fn new(reader: R) -> Parser { Parser { reader: reader, buf: vec![], pos: 0, } } pub fn update_buf(&mut self) { self.buf.clear(); self.pos = 0; loop { let (len, complete) = { let buf2 = self.reader.fill_buf().unwrap(); self.buf.extend_from_slice(buf2); let len = buf2.len(); (len, buf2[len - 1] <= 0x20) }; self.reader.consume(len); if complete { break; } } } pub fn next(&mut self) -> Result { loop { let mut begin = self.pos; while begin < self.buf.len() && (self.buf[begin] <= 0x20) { begin += 1; } let mut end = begin; while end < self.buf.len() && (self.buf[end] > 0x20) { end += 1; } if begin != self.buf.len() { self.pos = end; return unsafe { str::from_utf8_unchecked(&self.buf[begin..end]) }.parse::(); } else { self.update_buf(); } } } pub fn fast_i64(&mut self) -> i64 { loop { let mut begin = self.pos; while begin < self.buf.len() && (self.buf[begin] <= 0x20) { begin += 1; } if begin == self.buf.len() { self.update_buf(); continue; } let mut res = 0; let (is_positive, mut end) = match self.buf[begin] { b'+' => (true, begin + 1), b'-' => (false, begin + 1), _ => (true, begin), }; while end < self.buf.len() && (self.buf[end] > 0x20) { res = res * 10 + (self.buf[end] as i64 - '0' as i64); end += 1; } if begin != self.buf.len() { self.pos = end; return if is_positive { res } else { -res }; } else { self.update_buf(); } } } } #[allow(unused_imports)] use std::cmp::*; use std::marker::PhantomData; use std::ops::*; pub trait ModP { fn as_u64() -> u64; } #[allow(non_camel_case_types)] #[derive(Clone, Copy, Debug)] pub struct Mod_1_000_000_007(); impl ModP for Mod_1_000_000_007 { fn as_u64() -> u64 { 1_000_000_007 } } #[allow(non_camel_case_types)] #[derive(Clone, Copy, Debug)] pub struct Mod_998_244_353(); impl ModP for Mod_998_244_353 { fn as_u64() -> u64 { 998_244_353 } } #[derive(Clone, Copy, PartialEq, Debug)] pub struct Modular(u32, PhantomData

); impl Modular

{ pub fn new(x: u32) -> Modular

{ Modular((x as u64 % P::as_u64()) as u32, PhantomData) } pub fn pow(self, n: u64) -> Modular

{ if n == 0 { return Modular(1, PhantomData); } let t = self.pow(n / 2); if n % 2 == 0 { t * t } else { t * t * self } } pub fn as_u32(self) -> u32 { self.0 } } impl Add for Modular

{ type Output = Self; fn add(self, rhs: Self) -> Self::Output { let t = (self.0 + rhs.0) as u64; let u = if t < P::as_u64() { t } else { t - P::as_u64() }; Modular(u as u32, PhantomData) } } impl AddAssign for Modular

{ fn add_assign(&mut self, rhs: Self) { *self = *self + rhs; } } impl Sub for Modular

{ type Output = Self; fn sub(self, rhs: Self) -> Self::Output { let t = if self.0 >= rhs.0 { self.0 as u64 - rhs.0 as u64 } else { self.0 as u64 + P::as_u64() - rhs.0 as u64 }; assert!(t < P::as_u64()); Modular(t as u32, PhantomData) } } impl SubAssign for Modular

{ fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs; } } impl Neg for Modular

{ type Output = Modular

; fn neg(self) -> Modular

{ Modular((P::as_u64() - self.0 as u64) as u32, PhantomData) } } impl Mul for Modular

{ type Output = Self; fn mul(self, rhs: Self) -> Self::Output { Modular( ((self.0 as u64 % P::as_u64()) * (rhs.0 as u64 % P::as_u64()) % P::as_u64()) as u32, PhantomData, ) } } impl MulAssign for Modular

{ fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs; } } impl Div for Modular

{ type Output = Self; fn div(self, rhs: Self) -> Self::Output { if rhs.0 == 0 { loop {} } assert!(rhs.0 != 0); self * rhs.pow(P::as_u64() - 2) } } impl DivAssign for Modular

{ fn div_assign(&mut self, rhs: Self) { *self = *self / rhs; } } pub fn gen_fact_table(n: usize) -> Vec> { let mut res = vec![Modular::

::new(1); n + 1]; for i in 0..n { res[i + 1] = res[i] * Modular::

::new((i + 1) as u32); } res } pub fn gen_inv_table(n: usize) -> Vec> { let mut res = vec![Modular::

::new(0); n + 1]; res[1] = Modular::

::new(1); for i in 2..n + 1 { res[i] = -res[P::as_u64() as usize % i] * Modular::

::new((P::as_u64() / i as u64) as u32); } res } fn main() { input! { new_stdin_parser = parser, } let res = solve(&mut parser); print!("{}", res); } /*------------------------------------------------------------------*/ /*-------------------------- end template --------------------------*/ /*------------------------------------------------------------------*/ type Mod = Modular; fn get_d(x: usize) -> usize { let mut res = 0; let mut x = x; while x != 0 { res += 1; x /= 2; } res } use std::fmt::Write; fn solve(parser: &mut Parser) -> String { let mut buf = String::new(); input! { parser = parser, d: usize, l: usize, r: usize, k: usize, } let facts = gen_fact_table::(1 << 21); let mut base = Mod::new(1); for i in 0..d { base *= facts[1 << i]; } let l_d = get_d(l); let r_d = get_d(r); for lca_d in 1..l_d { if k == (l_d - lca_d) + (r_d - lca_d) { let res = base * Mod::new((1 << (l_d - lca_d - 1)) as u32) * Mod::new((1 << (r_d - l_d)) as u32) / Mod::new((1 << (r_d - 1)) - 1); writeln!(buf, "{}", res.as_u32()); return buf; } } if k == r_d - l_d { let res = base / Mod::new(1 << (l_d - 1)); writeln!(buf, "{}", res.as_u32()); return buf; } writeln!(buf, "0"); buf }