// SNIPPET read
pub trait Readable {
    type Output;
    fn words_count() -> usize;
    fn read_words(words: &[&str]) -> Result<Self::Output, String>;
}
#[macro_export]
macro_rules! readable {
    ( $t:ty, $words_count:expr, |$words:ident| $read_words:expr ) => {
        impl Readable for $t {
            type Output = $t;
            fn words_count() -> usize { $words_count }
            fn read_words($words: &[&str]) -> Result<$t, String> {
                Ok($read_words)
            }
        }
    };
}
readable!((), 1, |_ss| ());
readable!(String, 1, |ss| ss[0].to_string());
impl Readable for char {
    type Output = char;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<char, String> {
        let chars: Vec<char> = words[0].chars().collect();
        if chars.len() == 1 {
            Ok(chars[0])
        } else {
            Err(format!("cannot parse `{}` as a char", words[0]))
        }
    }
}
pub struct Chars();
impl Readable for Chars {
    type Output = Vec<char>;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<Vec<char>, String> {
        Ok(words[0].chars().collect())
    }
}
impl Readable for i8 {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<i8, String> {
        use std::str::FromStr;
        <i8>::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(i8))
        })
    }
}
impl Readable for u8 {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<u8, String> {
        use std::str::FromStr;
        <u8>::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(u8))
        })
    }
}
impl Readable for i16 {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<i16, String> {
        use std::str::FromStr;
        <i16>::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(i16))
        })
    }
}
impl Readable for u16 {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<u16, String> {
        use std::str::FromStr;
        <u16>::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(u16))
        })
    }
}
impl Readable for i32 {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<i32, String> {
        use std::str::FromStr;
        <i32>::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(i32))
        })
    }
}
impl Readable for u32 {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<u32, String> {
        use std::str::FromStr;
        <u32>::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(u32))
        })
    }
}
impl Readable for i64 {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<i64, String> {
        use std::str::FromStr;
        <i64>::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(i64))
        })
    }
}
impl Readable for u64 {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<u64, String> {
        use std::str::FromStr;
        <u64>::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(u64))
        })
    }
}
impl Readable for isize {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<isize, String> {
        use std::str::FromStr;
        <isize>::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(isize))
        })
    }
}
impl Readable for usize {
    type Output = Self;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<usize, String> {
        use std::str::FromStr;
        <usize>::from_str(words[0]).map_err(|_| {
            format!("cannot parse `{}` as {}", words[0], stringify!(usize))
        })
    }
}
#[allow(non_camel_case_types)]
pub struct u8_;
impl Readable for u8_ {
    type Output = u8;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        <u8>::read_words(words).map(|n| n-1)
    }
}
#[allow(non_camel_case_types)]
pub struct u16_;
impl Readable for u16_ {
    type Output = u16;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        <u16>::read_words(words).map(|n| n-1)
    }
}
#[allow(non_camel_case_types)]
pub struct u32_;
impl Readable for u32_ {
    type Output = u32;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        <u32>::read_words(words).map(|n| n-1)
    }
}
#[allow(non_camel_case_types)]
pub struct u64_;
impl Readable for u64_ {
    type Output = u64;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        <u64>::read_words(words).map(|n| n-1)
    }
}
#[allow(non_camel_case_types)]
pub struct usize_;
impl Readable for usize_ {
    type Output = usize;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        <usize>::read_words(words).map(|n| n-1)
    }
}
impl<T1: Readable, T2: Readable> Readable for (T1, T2) {
    type Output = (T1::Output, T2::Output);
    fn words_count() -> usize {
        T1::words_count() + T2::words_count()
    }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        assert_eq!(words.len(), Self::words_count());
        let mut start = 0;
        let count1 = T1::words_count();
        let val1 = T1::read_words(&words[start .. start+count1])?;
        start += count1;
        let val2 = T2::read_words(&words[start..])?;
        Ok((val1, val2))
    }
}
impl<T1: Readable, T2: Readable, T3: Readable> Readable for (T1, T2, T3) {
    type Output = (T1::Output, T2::Output, T3::Output);
    fn words_count() -> usize {
        T1::words_count() + T2::words_count() + T3::words_count()
    }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        assert_eq!(words.len(), Self::words_count());
        let mut start = 0;
        let count1 = T1::words_count();
        let val1 = T1::read_words(&words[start .. start+count1])?;
        start += count1;
        let count2 = T2::words_count();
        let val2 = T2::read_words(&words[start .. start+count2])?;
        start += count2;
        let val3 = T3::read_words(&words[start..])?;
        Ok((val1, val2, val3))
    }
}
impl<T1: Readable, T2: Readable, T3: Readable, T4: Readable> Readable for (T1, T2, T3, T4) {
    type Output = (T1::Output, T2::Output, T3::Output, T4::Output);
    fn words_count() -> usize {
        T1::words_count() + T2::words_count() + T3::words_count() + T4::words_count()
    }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        assert_eq!(words.len(), Self::words_count());
        let mut start = 0;
        let count1 = T1::words_count();
        let val1 = T1::read_words(&words[start .. start+count1])?;
        start += count1;
        let count2 = T2::words_count();
        let val2 = T2::read_words(&words[start .. start+count2])?;
        start += count2;
        let count3 = T3::words_count();
        let val3 = T3::read_words(&words[start .. start+count3])?;
        start += count3;
        let val4 = T4::read_words(&words[start..])?;
        Ok((val1, val2, val3, val4))
    }
}
impl<T1: Readable, T2: Readable, T3: Readable, T4: Readable, T5: Readable> Readable for (T1, T2, T3, T4, T5) {
    type Output = (T1::Output, T2::Output, T3::Output, T4::Output, T5::Output);
    fn words_count() -> usize {
        T1::words_count() + T2::words_count() + T3::words_count() + T4::words_count() + T5::words_count()
    }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        assert_eq!(words.len(), Self::words_count());
        let mut start = 0;
        let count1 = T1::words_count();
        let val1 = T1::read_words(&words[start .. start+count1])?;
        start += count1;
        let count2 = T2::words_count();
        let val2 = T2::read_words(&words[start .. start+count2])?;
        start += count2;
        let count3 = T3::words_count();
        let val3 = T3::read_words(&words[start .. start+count3])?;
        start += count3;
        let count4 = T4::words_count();
        let val4 = T4::read_words(&words[start .. start+count4])?;
        start += count4;
        let val5 = T5::read_words(&words[start..])?;
        Ok((val1, val2, val3, val4, val5))
    }
}
impl<T1: Readable, T2: Readable, T3: Readable, T4: Readable, T5: Readable, T6: Readable> Readable for (T1, T2, T3, T4, T5, T6) {
    type Output = (T1::Output, T2::Output, T3::Output, T4::Output, T5::Output, T6::Output);
    fn words_count() -> usize {
        T1::words_count() + T2::words_count() + T3::words_count() + T4::words_count() + T5::words_count() + T6::words_count()
    }
    fn read_words(words: &[&str]) -> Result<Self::Output, String> {
        assert_eq!(words.len(), Self::words_count());
        let mut start = 0;
        let count1 = T1::words_count();
        let val1 = T1::read_words(&words[start .. start+count1])?;
        start += count1;
        let count2 = T2::words_count();
        let val2 = T2::read_words(&words[start .. start+count2])?;
        start += count2;
        let count3 = T3::words_count();
        let val3 = T3::read_words(&words[start .. start+count3])?;
        start += count3;
        let count4 = T4::words_count();
        let val4 = T4::read_words(&words[start .. start+count4])?;
        start += count4;
        let count5 = T5::words_count();
        let val5 = T5::read_words(&words[start .. start+count5])?;
        start += count5;
        let val6 = T6::read_words(&words[start..])?;
        Ok((val1, val2, val3, val4, val5, val6))
    }
}
pub trait ReadableFromLine {
    type Output;
    fn read_line(line: &str) -> Result<Self::Output, String>;
}
fn split_into_words(line: &str) -> Vec<&str> {
    #[allow(deprecated)]
    line.trim_right_matches('\n').split_whitespace().collect()
}
impl<T: Readable> ReadableFromLine for T {
    type Output = T::Output;
    fn read_line(line: &str) -> Result<T::Output, String> {
        let words = split_into_words(line);
        if words.len() != T::words_count() {
            return Err(format!("line `{}` has {} words, expected {}",
                               line, words.len(), T::words_count()));
        }
        T::read_words(&words)
    }
}
fn read_words_into_vec<T: Readable>(words: &[&str], line: &str) -> Result<Vec<T::Output>, String> {
    let n = T::words_count();
    assert_eq!(words.len() % n, 0);
    let mut result = Vec::new();
    for chunk in words.chunks(n) {
        match T::read_words(chunk) {
            Ok(v) => result.push(v),
            Err(msg) => {
                let fragment_msg = if n == 1 {
                    format!("word {}", result.len())
                } else {
                    let l = result.len();
                    format!("words {}-{}", n*l + 1, (n+1) * l)
                };
                return Err(format!(
                    "{} of line `{}`: {}", fragment_msg, line, msg
                ));
            }
        }
    }
    Ok(result)
}
fn split_into_words_for_collection<T: Readable>(
    line: &str, prefix_words_count: usize
) -> Result<Vec<&str>, String> {
    let n = T::words_count();
    let words = split_into_words(line);
    if words.len() < prefix_words_count {
        return Err(
            format!("line `{}` has {} words, expected at least {}",
                    line, words.len(), prefix_words_count)
        );
    }
    if (words.len() - prefix_words_count) % T::words_count() != 0 {
        return Err(
            format!("line `{}` has {} words, expected {} + {}n",
                    line, words.len(), prefix_words_count, n)
        );
    }
    Ok(words)
}
#[macro_export]
macro_rules! readable_collection {
    ($u:ident => $collection_in:ty, $collection_out:ty) => {
        readable_collection!($u: [] => $collection_in, $collection_out);
    };
    ($u:ident : [ $( $bound:path ),* ] => $collection_in:ty, $collection_out:ty) => {
        impl<$u: Readable> ReadableFromLine for $collection_in
        where
            <$u as Readable>::Output: Sized $(+ $bound)*
        {
            type Output = $collection_out;
            fn read_line(line: &str) -> Result<Self::Output, String> {
                let words = split_into_words_for_collection::<$u>(line, 0)?;
                Ok(read_words_into_vec::<$u>(&words, line)?.into_iter().collect())
            }
        }
        impl<T1: Readable, $u: Readable> ReadableFromLine for (T1, $collection_in)
        where
            <$u as Readable>::Output: Sized $(+ $bound)*
        {
            type Output = (T1::Output, $collection_out);
            fn read_line(line: &str) -> Result<Self::Output, String> {
                let prefix_len = T1::words_count();
                let words = split_into_words_for_collection::<$u>(line, prefix_len)?;
                let val1 = T1::read_words(&words[..prefix_len])?;
                let rest = read_words_into_vec::<$u>(&words[prefix_len..], line)?;
                Ok((val1, rest.into_iter().collect()))
            }
        }
        impl<T1: Readable, T2: Readable, $u: Readable> ReadableFromLine for (T1, T2, $collection_in)
        where
            <$u as Readable>::Output: Sized $(+ $bound)*
        {
            type Output = (T1::Output, T2::Output, $collection_out);
            fn read_line(line: &str) -> Result<Self::Output, String> {
                let prefix_len = <(T1, T2)>::words_count();
                let words = split_into_words_for_collection::<$u>(line, prefix_len)?;
                let mut start = 0;
                let count1 = T1::words_count();
                let val1 = T1::read_words(&words[start .. start+count1])?;
                start += count1;
                let count2 = T2::words_count();
                let val2 = T2::read_words(&words[start .. start+count2])?;
                let rest = read_words_into_vec::<$u>(&words[prefix_len..], line)?;
                Ok((val1, val2, rest.into_iter().collect()))
            }
        }
        impl<T1: Readable, T2: Readable, T3: Readable, $u: Readable> ReadableFromLine for (T1, T2, T3, $collection_in)
        where
            <$u as Readable>::Output: Sized $(+ $bound)*
        {
            type Output = (T1::Output, T2::Output, T3::Output, $collection_out);
            fn read_line(line: &str) -> Result<Self::Output, String> {
                let prefix_len = <(T1, T2, T3)>::words_count();
                let words = split_into_words_for_collection::<$u>(line, prefix_len)?;
                let mut start = 0;
                let count1 = T1::words_count();
                let val1 = T1::read_words(&words[start .. start+count1])?;
                start += count1;
                let count2 = T2::words_count();
                let val2 = T2::read_words(&words[start .. start+count2])?;
                start += count2;
                let count3 = T3::words_count();
                let val3 = T3::read_words(&words[start .. start+count3])?;
                let rest = read_words_into_vec::<$u>(&words[prefix_len..], line)?;
                Ok((val1, val2, val3, rest.into_iter().collect()))
            }
        }
        impl<T1: Readable, T2: Readable, T3: Readable, T4: Readable, $u: Readable> ReadableFromLine for (T1, T2, T3, T4, $collection_in)
        where
            <$u as Readable>::Output: Sized $(+ $bound)*
        {
            type Output = (T1::Output, T2::Output, T3::Output, T4::Output, $collection_out);
            fn read_line(line: &str) -> Result<Self::Output, String> {
                let prefix_len = <(T1, T2, T3, T4)>::words_count();
                let words = split_into_words_for_collection::<$u>(line, prefix_len)?;
                let mut start = 0;
                let count1 = T1::words_count();
                let val1 = T1::read_words(&words[start .. start+count1])?;
                start += count1;
                let count2 = T2::words_count();
                let val2 = T2::read_words(&words[start .. start+count2])?;
                start += count2;
                let count3 = T3::words_count();
                let val3 = T3::read_words(&words[start .. start+count3])?;
                start += count3;
                let count4 = T4::words_count();
                let val4 = T4::read_words(&words[start .. start+count4])?;
                let rest = read_words_into_vec::<$u>(&words[prefix_len..], line)?;
                Ok((val1, val2, val3, val4, rest.into_iter().collect()))
            }
        }
    };
}
readable_collection!(U => Vec<U>, Vec<U::Output>);
pub fn read<T: ReadableFromLine>() -> T::Output {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    T::read_line(&line).unwrap()
}
#[macro_export]
macro_rules! read {
    () => {
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
    };
    ( $pat:pat = $t:ty ) => {
        let $pat = read::<$t>();
    };
    ( $( $pat:pat = $t:ty ),+ ) => {
        read!(($($pat),*) = ($($t),*));
    };
}
#[macro_export]
macro_rules! readls {
    ( $( $pat:pat = $t:ty ),+ ) => {
        $(
            read!($pat = $t);
        )*
    };
}
pub fn readx<T: ReadableFromLine>() -> Vec<T::Output> {
    use std::io::{self, BufRead};
    let stdin = io::stdin();
    let result = stdin.lock().lines().map(|line_result| {
        let line = line_result.expect("read from stdin failed");
        T::read_line(&line).unwrap()
    }).collect();
    result
}
#[macro_export]
macro_rules! readx_loop {
    ( |$pat:pat = $t:ty| $body:expr ) => {
        {
            use std::io::BufRead;
            let stdin = std::io::stdin();
            for line in stdin.lock().lines() {
                let line = line.expect("read from stdin failed");
                let $pat = <$t>::read_line(&line).unwrap();
                $body
            }
        }
    };
    ( |$($pat:pat = $t:ty),*| $body:expr ) => {
        readx_loop!(|($($pat),*) = ($($t),*)| $body);
    };
}
pub fn readn<T: ReadableFromLine>(n: usize) -> Vec<T::Output> {
    use std::io::{self, BufRead};
    let stdin = io::stdin();
    let result: Vec<T::Output> = stdin.lock().lines().take(n).map(|line_result| {
        let line = line_result.expect("read from stdin failed");
        T::read_line(&line).unwrap()
    }).collect();
    if result.len() < n {
        panic!("expected reading {} lines, but only {} lines are read",
               n, result.len());
    }
    result
}
#[macro_export]
macro_rules! readn_loop {
    ( $n:expr, |$pat:pat = $t:ty| $body:expr ) => {
        {
            use std::io::BufRead;
            let stdin = std::io::stdin();
            let mut lock = stdin.lock();
            for _ in 0..$n {
                let mut line = String::new();
                lock.read_line(&mut line).expect("read from stdin failed");
                let $pat = <$t>::read_line(&line).unwrap();
                $body
            }
        }
    };
    ( $n:expr, |$($pat:pat = $t:ty),*| $body:expr ) => {
        readn_loop!($n, |($($pat),*) = ($($t),*)| $body);
    };
}
pub trait Words {
    fn read<T: Readable>(&self) -> T::Output;
}
impl<'a> Words for [&'a str] {
    fn read<T: Readable>(&self) -> T::Output {
        T::read_words(self).unwrap()
    }
}
impl<'a> Words for &'a str {
    fn read<T: Readable>(&self) -> T::Output {
        T::read_words(&[self]).unwrap()
    }
}

// SNIPPET iter
#[derive(Clone)]
pub struct StepBy<I> {
    iter: I,
    step: usize,
    first_take: bool
}
impl<I: Iterator> Iterator for StepBy<I> {
    type Item = I::Item;
    fn next(&mut self) -> Option<Self::Item> {
        if self.first_take {
            self.first_take = false;
            self.iter.next()
        } else {
            self.iter.nth(self.step)
        }
    }
}
pub struct Chunks<I: Iterator> {
    iter: I,
    size: usize
}
impl<I: Iterator> Iterator for Chunks<I> {
    type Item = Vec<I::Item>;
    fn next(&mut self) -> Option<Self::Item> {
        let first = self.iter.next();
        if first.is_none() {
            return None;
        }
        let mut chunk = Vec::with_capacity(self.size);
        chunk.push(first.unwrap());
        for _ in 0..self.size-1 {
            match self.iter.next() {
                Some(x) => chunk.push(x),
                None => break
            }
        }
        Some(chunk)
    }
}
#[derive(Clone)]
pub struct LScan<I: Iterator, S: Clone, F: FnMut(&S, I::Item) -> S> {
    iter: I,
    state: Option<S>,
    f: F,
}
impl<I: Iterator, S: Clone, F> Iterator for LScan<I, S, F>
where
    F: FnMut(&S, I::Item) -> S,
{
    type Item = S;
    fn next(&mut self) -> Option<S> {
        if self.state.is_none() {
            return None;
        }
        let state_inner = self.state.take().unwrap();
        if let Some(item) = self.iter.next() {
            self.state = Some((self.f)(&state_inner, item));
        }
        Some(state_inner)
    }
}
pub struct Flatten<I: Iterator>
where
    I::Item: IntoIterator
{
    outer_iter: I,
    inner_iter: Option<<<I as Iterator>::Item as IntoIterator>::IntoIter>
}
impl<I, J> Iterator for Flatten<I>
where
    I: Iterator<Item = J>,
    J: IntoIterator
{
    type Item = <<J as IntoIterator>::IntoIter as Iterator>::Item;
    fn next(&mut self) -> Option<J::Item> {
        loop {
            if let Some(inner_iter) = self.inner_iter.as_mut() {
                if let item@Some(_) = inner_iter.next() {
                    return item
                }
            }
            match self.outer_iter.next() {
                None => return None,
                Some(inner) => self.inner_iter = Some(inner.into_iter())
            }
        }
    }
}
/*
impl<I, J> DoubleEndedIterator for Flatten<I>
where
    I: DoubleEndedIterator,
    J: DoubleEndedIterator,
    I::Item: J {}
*/
pub struct GroupBy<K: Eq, I: Iterator, F: FnMut(&I::Item) -> K> {
    cur: Option<(I::Item, K)>,
    iter: I,
    key_fn: F
}
impl<K: Eq, I: Iterator, F: FnMut(&I::Item) -> K> Iterator for GroupBy<K, I, F> {
    type Item = (K, Vec<I::Item>);
    fn next(&mut self) -> Option<(K, Vec<I::Item>)> {
        let cur = self.cur.take();
        cur.map(|(item, key)| {
            let mut group = vec![item];
            loop {
                let next = self.iter.next();
                match next {
                    Some(next_item) => {
                        let next_key = (self.key_fn)(&next_item);
                        if key == next_key {
                            group.push(next_item);
                        } else {
                            self.cur = Some((next_item, next_key));
                            break;
                        }
                    }
                    None => {
                        self.cur = None;
                        break;
                    }
                }
            }
            (key, group)
        })
    }
}
pub struct RunLength<I: Iterator> {
    cur: Option<I::Item>,
    iter: I
}
impl<I: Iterator> Iterator for RunLength<I> where I::Item: Eq {
    type Item = (I::Item, usize);
    fn next(&mut self) -> Option<(I::Item, usize)> {
        let cur = self.cur.take();
        cur.map(|value| {
            let mut length = 1;
            loop {
                let next = self.iter.next();
                match next {
                    Some(next_value) => {
                        if value == next_value {
                            length += 1;
                        } else {
                            self.cur = Some(next_value);
                            break;
                        }
                    }
                    None => {
                        self.cur = None;
                        break;
                    }
                }
            }
            (value, length)
        })
    }
}
pub trait IteratorExt: Iterator {
    fn step_by_(self, step: usize) -> StepBy<Self> where Self: Sized {
        assert_ne!(step, 0);
        StepBy {
            iter: self,
            step: step - 1,
            first_take: true
        }
    }
    fn for_each<F: FnMut(Self::Item)>(self, mut f: F) where Self: Sized {
        for item in self {
            f(item);
        }
    }
    fn chunks(self, size: usize) -> Chunks<Self> where Self: Sized {
        assert!(size > 0);
        Chunks {
            iter: self,
            size: size
        }
    }
    fn lscan<S: Clone, F>(self, state: S, f: F) -> LScan<Self, S, F>
    where
        Self: Sized,
        F: FnMut(&S, Self::Item) -> S,
    {
        LScan {
            iter: self,
            state: Some(state),
            f: f,
        }
    }
    fn get_unique(mut self) -> Option<Self::Item> where Self: Sized, Self::Item: Eq {
        let first_opt = self.next();
        first_opt.and_then(|first| {
            if self.all(|item| item == first) { Some(first) } else { None }
        })
    }
    fn flatten(mut self) -> Flatten<Self> where Self: Sized, Self::Item: IntoIterator {
        let inner_opt = self.next();
        Flatten {
            outer_iter: self,
            inner_iter: inner_opt.map(|inner| inner.into_iter())
        }
    }
    fn group_by<K: Eq, F: FnMut(&Self::Item) -> K>(mut self, mut f: F) -> GroupBy<K, Self, F> where Self: Sized {
        let next = self.next();
        GroupBy {
            cur: next.map(|item| {
                let key = f(&item);
                (item, key)
            }),
            iter: self,
            key_fn: f
        }
    }
    fn run_length(mut self) -> RunLength<Self> where Self: Sized, Self::Item: Eq {
        RunLength {
            cur: self.next(),
            iter: self
        }
    }
    fn join<T: std::fmt::Display>(mut self, sep: T) -> String
    where
        Self: Sized, Self::Item: std::fmt::Display
    {
        let mut result = String::new();
        if let Some(first) = self.next() {
            result.push_str(&format!("{}", first));
        }
        for s in self {
            result.push_str(&format!("{}{}", sep, s));
        }
        result
    }
    fn cat(self) -> String where Self: Sized, Self::Item: std::fmt::Display { self.join("") }
}
impl<I: Iterator> IteratorExt for I {}
pub struct Unfold<T, F> where F: FnMut(&T) -> Option<T> {
    state: Option<T>,
    f: F
}
impl<T, F> Iterator for Unfold<T, F> where F: FnMut(&T) -> Option<T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        if self.state.is_none() {
            return None;
        }
        let state_inner = self.state.take().unwrap();
        self.state = (self.f)(&state_inner);
        Some(state_inner)
    }
}
pub fn unfold<T, F>(init: T, f: F) -> Unfold<T, F> where F: FnMut(&T) -> Option<T> {
    Unfold { state: Some(init), f: f }
}
pub struct Iterate<T, F> where F: FnMut(&T) -> T {
    state: T,
    f: F
}
impl<T, F> Iterator for Iterate<T, F> where F: FnMut(&T) -> T {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        use std::mem::swap;
        let mut state = (self.f)(&self.state);
        swap(&mut state, &mut self.state);
        Some(state)
    }
}
pub fn iterate<T, F>(init: T, f: F) -> Iterate<T, F>
where
    F: FnMut(&T) -> T,
{
    Iterate { state: init, f: f }
}

// SNIPPET modp
pub type ModPBase = u64;
pub type ModPModulus = u32;
static mut MODULUS: ModPBase = 0;
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub struct ModP {
    base: ModPBase
}
impl ModP {
    pub unsafe fn set_mod(modulus: ModPModulus) -> Result<(), String> {
        if modulus <= 1 {
            return Err(format!("{} is not a prime number.", modulus));
        }
        if modulus >= 4 {
            if modulus % 2 == 0 || modulus % 3 == 0 {
                return Err(format!("{} is not a prime number.", modulus));
            }
            let mut divisor = 5;
            loop {
                if divisor * divisor > modulus {
                    break;
                }
                if modulus % divisor == 0 {
                    return Err(format!("{} is not a prime number.", modulus));
                }
                divisor += 2;
                if divisor * divisor > modulus {
                    break;
                }
                if modulus % divisor == 0 {
                    return Err(format!("{} is not a prime number.", modulus));
                }
                divisor += 4;
            }
        }
        MODULUS = modulus as ModPBase;
        Ok(())
    }
    pub fn new(n: ModPBase) -> ModP {
        if !cfg!(test) {
            assert!(unsafe { MODULUS } != 0,
                    "Call ModP::set_mod before using ModP.");
        }
        ModP { base: n % unsafe { MODULUS } }
    }
    pub unsafe fn new_unchecked(n: ModPBase) -> ModP {
        ModP { base: n }
    }
    pub fn base(&self) -> ModPBase {
        self.base
    }
    pub fn pow(self, exp: ModPBase) -> ModP {
        if exp == 0 { ModP::new(1) } else {
            let sub = self.pow(exp / 2);
            if exp % 2 == 0 {
                sub * sub
            } else {
                self * sub * sub
            }
        }
    }
    pub fn inv(self) -> ModP {
        assert!(self.base() != 0);
        self.pow(unsafe { MODULUS } - 2)
    }
    pub fn fact_cache() -> FactCache {
        FactCache {
            table: vec![ModP::new(1)]
        }
    }
    pub fn inv_cache() -> InvCache {
        InvCache {
            table: vec![ModP::new(0), ModP::new(1)]
        }
    }
    pub fn pow_cache(base: ModPBase) -> PowCache {
        PowCache {
            base: base,
            table: vec![ModP::new(1)]
        }
    }
    pub fn combinatorics_cache() -> CombinatoricsCache {
        CombinatoricsCache {
            facts: ModP::fact_cache(),
            invs: ModP::inv_cache(),
            finvs: vec![ModP::new(1)],
        }
    }
}
pub fn modp(x: ModPBase) -> ModP {
    ModP::new(x)
}
impl std::fmt::Display for ModP {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "{}", self.base())
    }
}
impl std::fmt::Debug for ModP {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "{} mod P", self.base())
    }
}
impl PartialEq<ModPBase> for ModP {
    fn eq(&self, other: &ModPBase) -> bool {
        self.base() == other % unsafe { MODULUS }
    }
}
impl PartialEq<ModP> for ModPBase {
    fn eq(&self, other: &ModP) -> bool {
        self % unsafe { MODULUS } == other.base() % unsafe { MODULUS }
    }
}
impl std::ops::Add for ModP {
    type Output = ModP;
    fn add(self, rhs: ModP) -> ModP {
        let m = unsafe { MODULUS };
        ModP { base: (self.base() + rhs.base() % m) % m }
    }
}
impl std::ops::Add<ModPBase> for ModP {
    type Output = ModP;
    fn add(self, rhs: ModPBase) -> ModP {
        self + ModP::new(rhs)
    }
}
impl std::ops::Add<ModP> for ModPBase {
    type Output = ModP;
    fn add(self, rhs: ModP) -> ModP {
        ModP::new(self) + rhs.base()
    }
}
impl std::ops::AddAssign for ModP {
    fn add_assign(&mut self, rhs: ModP) {
        *self = *self + rhs
    }
}
impl std::ops::AddAssign<ModPBase> for ModP {
    fn add_assign(&mut self, rhs: ModPBase) {
        *self = *self + ModP::new(rhs)
    }
}
impl std::ops::Neg for ModP {
    type Output = ModP;
    fn neg(self) -> ModP {
        ModP::new(unsafe { MODULUS } - self.base())
    }
}
impl std::ops::Sub for ModP {
    type Output = ModP;
    fn sub(self, rhs: ModP) -> ModP {
        self + (-rhs)
    }
}
impl std::ops::Sub<ModPBase> for ModP {
    type Output = ModP;
    fn sub(self, rhs: ModPBase) -> ModP {
        self - ModP::new(rhs)
    }
}
impl std::ops::Sub<ModP> for ModPBase {
    type Output = ModP;
    fn sub(self, rhs: ModP) -> ModP {
        ModP::new(self) - rhs
    }
}
impl std::ops::SubAssign for ModP {
    fn sub_assign(&mut self, rhs: ModP) {
        *self = *self - rhs;
    }
}
impl std::ops::SubAssign<ModPBase> for ModP {
    fn sub_assign(&mut self, rhs: ModPBase) {
        *self = *self - ModP::new(rhs)
    }
}
impl std::ops::Mul for ModP {
    type Output = ModP;
    fn mul(self, rhs: ModP) -> ModP {
        let m = unsafe { MODULUS };
        ModP { base: self.base() * (rhs.base() % m) % m }
    }
}
impl std::ops::Mul<ModPBase> for ModP {
    type Output = ModP;
    fn mul(self, rhs: ModPBase) -> ModP {
        self * ModP::new(rhs)
    }
}
impl std::ops::Mul<ModP> for ModPBase {
    type Output = ModP;
    fn mul(self, rhs: ModP) -> ModP {
        ModP::new(self) * rhs.base()
    }
}
impl std::ops::MulAssign for ModP {
    fn mul_assign(&mut self, rhs: ModP) {
        *self = *self * rhs
    }
}
impl std::ops::MulAssign<ModPBase> for ModP {
    fn mul_assign(&mut self, rhs: ModPBase) {
        *self = *self * ModP::new(rhs)
    }
}
impl std::ops::Div for ModP {
    type Output = ModP;
    fn div(self, rhs: ModP) -> ModP {
        self * rhs.inv()
    }
}
impl std::ops::Div<ModPBase> for ModP {
    type Output = ModP;
    fn div(self, rhs: ModPBase) -> ModP {
        self * ModP::new(rhs).inv()
    }
}
impl std::ops::Div<ModP> for ModPBase {
    type Output = ModP;
    fn div(self, rhs: ModP) -> ModP {
        ModP::new(self) * rhs.inv()
    }
}
impl std::ops::DivAssign for ModP {
    fn div_assign(&mut self, rhs: ModP) {
        *self = *self / rhs;
    }
}
impl std::ops::DivAssign<ModPBase> for ModP {
    fn div_assign(&mut self, rhs: ModPBase) {
        *self = *self / ModP::new(rhs)
    }
}
impl std::iter::Sum for ModP {
    fn sum<I: Iterator<Item=ModP>>(iter: I) -> ModP {
        let mut ans = 0;
        for n in iter {
            ans += n.base();
        }
        ModP::new(ans)
    }
}
impl<'a> std::iter::Sum<&'a ModP> for ModP {
    fn sum<I: Iterator<Item=&'a ModP>>(iter: I) -> ModP {
        let mut ans = 0;
        for n in iter {
            ans += n.base();
        }
        ModP::new(ans)
    }
}
impl std::iter::Product for ModP {
    fn product<I: Iterator<Item=ModP>>(iter: I) -> ModP {
        let mut ans = unsafe { ModP::new_unchecked(1) };
        for n in iter {
            ans *= n;
        }
        ans
    }
}
impl<'a> std::iter::Product<&'a ModP> for ModP {
    fn product<I: Iterator<Item=&'a ModP>>(iter: I) -> ModP {
        let mut ans = unsafe { ModP::new_unchecked(1) };
        for &n in iter {
            ans *= n;
        }
        ans
    }
}
readable!(ModP, 1, |ws| ModP::new(ws[0].read::<ModPBase>()));
pub struct FactCache {
    table: Vec<ModP>
}
impl FactCache {
    pub fn get(&mut self, n: ModPBase) -> ModP {
        self.extend(n as usize);
        self.table[n as usize]
    }
    fn extend(&mut self, max: usize) {
        for i in self.table.len()..max+1 {
            let prev = self.table[i-1];
            self.table.push(prev * i as ModPBase);
        }
    }
}
pub struct InvCache {
    table: Vec<ModP>
}
impl InvCache {
    pub fn get(&mut self, n: ModPBase) -> ModP {
        assert!(n > 0);
        self.extend(n as usize);
        self.table[n as usize]
    }
    fn extend(&mut self, max: usize) {
        for i in self.table.len()..max+1 {
            let m = unsafe { MODULUS };
            let prev = self.table[m as usize % i];
            self.table.push(m / i as ModPBase * (-prev));
        }
    }
}
pub struct PowCache {
    base: ModPBase,
    table: Vec<ModP>
}
impl PowCache {
    pub fn get(&mut self, n: ModPBase) -> ModP {
        self.extend(n as usize);
        self.table[n as usize]
    }
    fn extend(&mut self, max: usize) {
        for i in self.table.len()..max+1 {
            let prev = self.table[i-1];
            self.table.push(prev * self.base);
        }
    }
}
pub struct CombinatoricsCache {
    facts: FactCache,
    invs: InvCache,
    finvs: Vec<ModP>,
}
impl CombinatoricsCache {
    pub fn choose(&mut self, n: ModPBase, m: ModPBase) -> ModP {
        if n < m {
            return ModP::new(0);
        }
        self.extend_finvs(std::cmp::max(m, n-m) as usize);
        self.fact(n) * self.finvs[m as usize] * self.finvs[(n-m) as usize]
    }
    pub fn homo(&mut self, n: ModPBase, m: ModPBase) -> ModP {
        if m == 0 {
            ModP::new(1)
        } else {
            self.choose(n+m-1, m)
        }
    }
    pub fn fact(&mut self, n: ModPBase) -> ModP {
        self.facts.get(n)
    }
    pub fn inv(&mut self, n: ModPBase) -> ModP {
        self.invs.get(n)
    }
    fn extend_finvs(&mut self, max: usize) {
        for i in self.finvs.len()..max+1 {
            let prev = self.finvs[i-1];
            self.finvs.push(prev * self.invs.get(i as ModPBase))
        }
    }
}

// SNIPPET dbg
#[macro_export]
#[cfg(local)]
macro_rules! dbg {
    () => {
        {
            use std::io::{self, Write};
            writeln!(io::stderr(), "{}: dbg", line!()).unwrap();
        }
    };
    ($e: expr) => {
        {
            use std::io::{self, Write};
            let result = $e;
            writeln!(io::stderr(), "{}: {} = {:?}",
                     line!(), stringify!($e), result)
                .unwrap();
            result
        }
    }
}
#[macro_export]
#[cfg(not(local))]
macro_rules! dbg {
    () => {};
    ($e: expr) => {
        { $e }
    }
}

// SNIPPET counter
#[derive(Clone)]
pub struct HashCounter<T: Eq + std::hash::Hash> {
    counter: std::collections::HashMap<T, usize>
}
pub struct HashCounterIter<'a, T: 'a> {
    iter: std::collections::hash_map::Iter<'a, T, usize>
}
impl<'a, T> Iterator for HashCounterIter<'a, T> {
    type Item = (&'a T, usize);
    fn next(&mut self) -> Option<(&'a T, usize)> {
        while let Some((key, &count)) = self.iter.next() {
            if count > 0 {
                return Some((key, count))
            }
        }
        None
    }
}
pub struct HashCounterIntoIter<T> {
    iter: std::collections::hash_map::IntoIter<T, usize>
}
impl<'a, T> Iterator for HashCounterIntoIter<T> {
    type Item = (T, usize);
    fn next(&mut self) -> Option<(T, usize)> {
        while let Some((key, count)) = self.iter.next() {
            if count > 0 {
                return Some((key, count))
            }
        }
        None
    }
}
pub struct HashCounterValues<'a, T: 'a> {
    iter: std::collections::hash_map::Values<'a, T, usize>
}
impl<'a, T> Iterator for HashCounterValues<'a, T> {
    type Item = usize;
    fn next(&mut self) -> Option<usize> {
        while let Some(&n) = self.iter.next() {
            if n > 0 {
                return Some(n)
            }
        }
        None
    }
}
impl<T: Eq + std::hash::Hash> HashCounter<T> {
    pub fn new() -> HashCounter<T> {
        HashCounter { counter: std::collections::HashMap::new() }
    }
    pub fn with_capacity(capacity: usize) -> HashCounter<T> {
        HashCounter { counter: std::collections::HashMap::with_capacity(capacity) }
    }
    pub fn values(&self) -> HashCounterValues<T> {
        HashCounterValues { iter: self.counter.values() }
    }
    pub fn iter(&self) -> HashCounterIter<T> {
        HashCounterIter { iter: self.counter.iter() }
    }
}
static HASH_COUNTER_ZERO: usize = 0;
impl<'a, T, Q: ?Sized> std::ops::Index<&'a Q> for HashCounter<T>
where
    T: Eq + std::hash::Hash + std::borrow::Borrow<Q>,
    Q: Eq + std::hash::Hash
{
    type Output = usize;
    fn index(&self, key: &Q) -> &usize {
        self.counter.get(key).unwrap_or(&HASH_COUNTER_ZERO)
    }
}
impl<'a, T, Q: ?Sized> std::ops::IndexMut<&'a Q> for HashCounter<T>
where
    T: Eq + std::hash::Hash + std::borrow::Borrow<Q>,
    Q: Eq + std::hash::Hash + std::borrow::ToOwned<Owned=T>
{
    fn index_mut(&mut self, key: &Q) -> &mut usize {
        self.counter.entry(key.to_owned()).or_insert(0)
    }
}
impl<T: std::hash::Hash + Eq> std::iter::FromIterator<T> for HashCounter<T> {
    fn from_iter<I>(iter: I) -> HashCounter<T> where I: IntoIterator<Item=T> {
        let mut counter = HashCounter::new();
        for item in iter {
            *counter.counter.entry(item).or_insert(0) += 1;
        }
        counter
    }
}
impl<T: std::hash::Hash + Eq> std::iter::IntoIterator for HashCounter<T> {
    type Item = (T, usize);
    type IntoIter = HashCounterIntoIter<T>;
    fn into_iter(self) -> HashCounterIntoIter<T> {
        HashCounterIntoIter { iter: self.counter.into_iter() }
    }
}
#[macro_export]
macro_rules! hash_counter {
    ($($item:expr),*) => {
        {
            let mut counter = HashCounter::new();
            $( counter[&$item] += 1; )*
            counter
        }
    }
}

// END SNIPPETS

fn main() {
    read!(_ = (), p = u32);
    read!(s = String);
    if p == 2 || p == 5 {
        let ans: u64 = (1u64..).zip(s.chars().map(|c| c.to_digit(10).unwrap() as u32)).map(|(c, d)| {
            if d % p == 0 { c } else { 0 }
        }).sum();
        println!("{}", ans);
        return;
    }

    unsafe { ModP::set_mod(p).unwrap(); }
    let inv10 = modp(10).inv();
    let invs = iterate(modp(1), |&x| x * inv10);
    let ps = (s.chars().zip(invs)).lscan(modp(0), |&acc, (c, m)| {
        acc + c.to_digit(10).unwrap() as u64 * m
    });
    let cnt: HashCounter<ModP> = ps.collect();
    let ans: usize = cnt.values().map(|x| x * (x-1) / 2).sum();
    println!("{}", ans);
}


Measured memory_bytes: 4352