macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; input_inner ! { iter , $ ( $ r ) * } } ; ( iter = $ iter : ident , $ ( $ r : tt ) * ) => { let s = { use std :: io :: Read ; let mut s = String :: new ( ) ; std :: io :: stdin ( ) . read_to_string ( & mut s ) . unwrap ( ) ; s } ; let mut $ iter = s . split_whitespace ( ) ; input_inner ! { $ iter , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let s = { use std :: io :: Read ; let mut s = String :: new ( ) ; std :: io :: stdin ( ) . read_to_string ( & mut s ) . unwrap ( ) ; s } ; let mut iter = s . split_whitespace ( ) ; input_inner ! { iter , $ ( $ r ) * } } ; }
macro_rules ! input_inner { ( $ iter : expr ) => { } ; ( $ iter : expr , ) => { } ; ( $ iter : expr , mut $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let mut $ var = read_value ! ( $ iter , $ t ) ; input_inner ! { $ iter $ ( $ r ) * } } ; ( $ iter : expr , mut $ var : ident $ ( $ r : tt ) * ) => { input_inner ! { $ iter , mut $ var : usize $ ( $ r ) * } } ; ( $ iter : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ iter , $ t ) ; input_inner ! { $ iter $ ( $ r ) * } } ; ( $ iter : expr , $ var : ident $ ( $ r : tt ) * ) => { input_inner ! { $ iter , $ var : usize $ ( $ r ) * } } ; }
macro_rules ! read_value { ( $ iter : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ iter , $ t ) ) ,* ) } ; ( $ iter : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ iter , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ iter : expr , { chars : $ base : expr } ) => { read_value ! ( $ iter , String ) . chars ( ) . map ( | c | ( c as u8 - $ base as u8 ) as usize ) . collect ::< Vec < usize >> ( ) } ; ( $ iter : expr , { char : $ base : expr } ) => { read_value ! ( $ iter , { chars : $ base } ) [ 0 ] } ; ( $ iter : expr , chars ) => { read_value ! ( $ iter , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ iter : expr , char ) => { read_value ! ( $ iter , chars ) [ 0 ] } ; ( $ iter : expr , usize1 ) => { read_value ! ( $ iter , usize ) - 1 } ; ( $ iter : expr , $ t : ty ) => { $ iter . next ( ) . unwrap ( ) . parse ::<$ t > ( ) . unwrap ( ) } ; }
pub trait Bisect: Copy {
    fn halve(self, other: Self) -> Self;
    fn section_end(self, other: Self) -> bool;
}
impl Bisect for u64 {
    fn halve(self, other: Self) -> Self {
        if self > other {
            other + (self - other) / 2
        } else {
            self + (other - self) / 2
        }
    }
    fn section_end(self, other: Self) -> bool {
        (if self > other {
            self - other
        } else {
            other - self
        }) <= 1
    }
}
impl Bisect for i64 {
    fn halve(self, other: Self) -> Self {
        (self + other) / 2
    }
    fn section_end(self, other: Self) -> bool {
        (self - other).abs() <= 1
    }
}
impl Bisect for f64 {
    fn halve(self, other: Self) -> Self {
        (self + other) / 2.
    }
    fn section_end(self, other: Self) -> bool {
        (self - other).abs() <= 1e-8
    }
}
pub fn binary_search<T: Bisect, F: Fn(T) -> bool>(f: F, ok: T, err: T) -> T {
    let mut ok = ok;
    let mut err = err;
    while !ok.section_end(err) {
        let m = ok.halve(err);
        if f(m) {
            ok = m;
        } else {
            err = m;
        }
    }
    ok
}
type Matrix = Vec<Vec<u64>>;
pub fn mat_eye(n: usize) -> Matrix {
    let mut v = vec![vec![0; n]; n];
    for i in 0..n {
        v[i][i] = 1;
    }
    v
}
pub fn mat_mul(x: &Matrix, y: &Matrix, m: u64) -> Matrix {
    let mut z = vec![vec![0; y[0].len()]; x.len()];
    for i in 0..x.len() {
        for j in 0..y[0].len() {
            for k in 0..x[0].len() {
                z[i][j] = (z[i][j] + x[i][k] * y[k][j] % m) % m;
            }
        }
    }
    z
}
pub fn mat_pow(x: Matrix, y: u64, m: u64) -> Matrix {
    let mut x = x;
    let mut y = y;
    let mut res = mat_eye(x.len());
    while y > 0 {
        if y & 1 == 1 {
            res = mat_mul(&res, &x, m);
        }
        x = mat_mul(&x, &x, m);
        y >>= 1;
    }
    res
}
fn main() {
    input! { l: u64, a: u64, b: u64, m: u64 };
    let mut v = vec![vec![0, a % m, 1]];
    for i in 0..18 {
        let t = 10u64.pow(i);
        let t1 = 10u64.pow(i + 1);
        let x = vec![vec![t1 % m, 0, 0], vec![1, 1, 0], vec![0, b % m, 1]];
        let k1 = binary_search(|k| t <= a + b * (k - 1), l + 1, 0u64) - 1;
        let k2 = binary_search(|k| t1 <= a + b * (k - 1), l + 1, 0u64) - 1;
        v = mat_mul(&v, &mat_pow(x, k2 - k1, m), m);
    }
    println!("{}", v[0][0]);
}


Measured memory_bytes: 4352