module mod_int
  implicit none
  private
  integer(8) :: modul
  integer :: capa
  
  type :: mint
    integer(8) :: n
  end type mint
  
  interface assignment(=)
    module procedure assign1, assign2
  end interface assignment(=)
  
  interface operator(+)
    module procedure add0, add1_1, add1_2, add2_1, add2_2
  end interface operator(+)
  
  interface operator(-)
    module procedure sub0, sub1_1, sub1_2, sub2_1, sub2_2
  end interface operator(-)
  
  interface operator(*)
    module procedure mul0, mul1_1, mul1_2, mul2_1, mul2_2
  end interface operator(*)
  
  interface operator(/)
    module procedure div0, div1_1, div1_2, div2_1, div2_2
  end interface operator(/)
  
  interface operator(**)
    module procedure pow1_1, pow1_2
  end interface operator(**)
  
  public :: mint
  public :: init, show, inv
  public :: assignment(=), operator(+), operator(-)
  public :: operator(*), operator(/), operator(**)
  
contains

  subroutine init(m)
    implicit none
    integer(8), intent(in) :: m
    modul = m
    capa = 5*ceiling(log10(real(m,8)))
    return
  end subroutine init
  
  subroutine show(a)
    implicit none
    type(mint), intent(in) :: a
    write(*,'(i0)') a%n
    return
  end subroutine show

  subroutine assign1(a,b)
    implicit none
    type(mint), intent(inout) :: a
    integer(8), intent(in) :: b
    integer(8) :: c
    c = b
    do while (c.lt.0_8)
      c = c + modul
    end do
    a%n = mod(c,modul)
    return
  end subroutine assign1
  
  subroutine assign2(a,b)
    implicit none
    type(mint), intent(inout) :: a
    integer, intent(in) :: b
    integer(8) :: c
    c = int(b,8)
    do while (c.lt.0_8)
      c = c + modul
    end do
    a%n = mod(c,modul)
    return
  end subroutine assign2
  
  function add0(a,b) result(r)
    implicit none
    type(mint), intent(in) :: a, b
    type(mint) :: r
    r%n = mod(a%n+b%n,modul)
    return
  end function add0
  
  function add1_1(a,b) result(r)
    implicit none
    type(mint), intent(in) :: a
    integer(8), intent(in) :: b
    type(mint) :: r
    call assign1(r,b)
    r = add0(a,r)
    return
  end function add1_1
  
  function add1_2(a,b) result(r)
    implicit none
    type(mint), intent(in) :: a
    integer, intent(in) :: b
    type(mint) :: r
    call assign2(r,b)
    r = add0(a,r)
    return
  end function add1_2
  
  function add2_1(a,b) result(r)
    implicit none
    integer(8), intent(in) :: a
    type(mint), intent(in) :: b
    type(mint) :: r
    call assign1(r,a)
    r = add0(r,b)
    return
  end function add2_1
  
  function add2_2(a,b) result(r)
    implicit none
    integer, intent(in) :: a
    type(mint), intent(in) :: b
    type(mint) :: r
    call assign2(r,a)
    r = add0(r,b)
    return
  end function add2_2
  
  function sub0(a,b) result(r)
    implicit none
    type(mint), intent(in) :: a, b
    type(mint) :: r
    r%n = mod(modul+a%n-b%n,modul)
    return
  end function sub0
  
  function sub1_1(a,b) result(r)
    implicit none
    type(mint), intent(in) :: a
    integer(8), intent(in) :: b
    type(mint) :: r
    call assign1(r,b)
    r = sub0(a,r)
    return
  end function sub1_1
  
  function sub1_2(a,b) result(r)
    implicit none
    type(mint), intent(in) :: a
    integer, intent(in) :: b
    type(mint) :: r
    call assign2(r,b)
    r = sub0(a,r)
    return
  end function sub1_2
  
  function sub2_1(a,b) result(r)
    implicit none
    integer(8), intent(in) :: a
    type(mint), intent(in) :: b
    type(mint) :: r
    call assign1(r,a)
    r = sub0(r,b)
    return
  end function sub2_1
  
  function sub2_2(a,b) result(r)
    implicit none
    integer, intent(in) :: a
    type(mint), intent(in) :: b
    type(mint) :: r
    call assign2(r,a)
    r = sub0(r,b)
    return
  end function sub2_2
  
  function mul0(a,b) result(r)
    implicit none
    type(mint), intent(in) :: a, b
    type(mint) :: r
    r%n = mod(a%n*b%n,modul)
    return
  end function mul0
  
  function mul1_1(a,b) result(r)
    implicit none
    type(mint), intent(in) :: a
    integer(8), intent(in) :: b
    type(mint) :: r
    call assign1(r,b)
    r = mul0(a,r)
    return
  end function mul1_1
  
  function mul1_2(a,b) result(r)
    implicit none
    type(mint), intent(in) :: a
    integer, intent(in) :: b
    type(mint) :: r
    call assign2(r,b)
    r = mul0(a,r)
    return
  end function mul1_2
  
  function mul2_1(a,b) result(r)
    implicit none
    integer(8), intent(in) :: a
    type(mint), intent(in) :: b
    type(mint) :: r
    call assign1(r,a)
    r = mul0(r,b)
    return
  end function mul2_1
  
  function mul2_2(a,b) result(r)
    implicit none
    integer, intent(in) :: a
    type(mint), intent(in) :: b
    type(mint) :: r
    call assign2(r,a)
    r = mul0(r,b)
    return
  end function mul2_2
  
  function div0(a,b) result(r)
    implicit none
    type(mint), intent(in) :: a, b
    type(mint) :: r
    r = mul0(a,inv(b))
    return
  end function div0
  
  function div1_1(a,b) result(r)
    implicit none
    type(mint), intent(in) :: a
    integer(8), intent(in) :: b
    type(mint) :: r
    call assign1(r,b)
    r = div0(a,r)
    return
  end function div1_1
  
  function div1_2(a,b) result(r)
    implicit none
    type(mint), intent(in) :: a
    integer, intent(in) :: b
    type(mint) :: r
    call assign2(r,b)
    r = div0(a,r)
    return
  end function div1_2
  
  function div2_1(a,b) result(r)
    implicit none
    integer(8), intent(in) :: a
    type(mint), intent(in) :: b
    type(mint) :: r
    call assign1(r,a)
    r = div0(r,b)
    return
  end function div2_1
  
  function div2_2(a,b) result(r)
    implicit none
    integer, intent(in) :: a
    type(mint), intent(in) :: b
    type(mint) :: r
    call assign2(r,a)
    r = div0(r,b)
    return
  end function div2_2
  
  function inv(a) result(b)
    implicit none
    type(mint), intent(in) :: a
    type(mint) :: b
    integer(8) :: k(capa), x0, x1, x2, y0, y1, y2
    integer :: u, i
    if (a%n.le.1_8) then
      b = a
      return
    end if
    k = 0_8
    x0 = modul
    x1 = a%n
    u = capa
    do i = 1, capa
      k(i) = x0/x1
      x2 = x0
      x0 = x1
      x1 = mod(x2,x1)
      if (x1.eq.0_8) then
        u = i-1
        exit
      end if
    end do
    y0 = 1_8
    y1 = -k(1)
    if (u.gt.1) then
      do i = 2, u
        y2 = y0-k(i)*y1
        y0 = y1
        y1 = y2
      end do
    end if
    call assign1(b,y1)
    return
  end function inv
  
  recursive function pow1_1(a,b) result(r)
    implicit none
    type(mint), intent(in) :: a
    integer(8), intent(in) :: b
    type(mint) :: r
    if (b.eq.0_8) then
      call assign2(r,1)
      return
    end if
    if (mod(b,2_8).eq.0_8) then
      r = pow1_1(a,b/2_8)
      r = mul0(r,r)
      return
    end if
    r = mul0(a,pow1_1(a,b-1_8))
    return
  end function pow1_1
  
  function pow1_2(a,b) result(r)
    implicit none
    type(mint), intent(in) :: a
    integer, intent(in) :: b
    type(mint) :: r
    r = pow1_1(a,int(b,8))
    return
  end function pow1_2
  
end module mod_int
program basics_in_education_and_learning
  use mod_int
  implicit none
  type(mint) :: ans, ten
  integer(8) :: l, a, b, m, last, t
  integer(8) :: inf, sup, na, nl
  integer :: i
  read(*,*) l, a, b, m
  call init(m)
  last = a+b*(l-1_8)
  t = 10_8
  ans = 0
  do i = 1, 18
    inf = t/10_8
    sup = t-1_8
    if (last.lt.inf) exit
    if (a.gt.sup) then
      t = 10_8*t
      cycle
    end if
    na = min(last,(((inf-a)+(b-1_8))/b)*b+a)
    if (a.ge.inf) na = a
    nl = ((sup-a)/b)*b+a
    if (last.le.sup) nl = last
    nl = (nl-na)/b+1_8
    ten = t
    ans = ans*(ten**nl)+f(nl,t)*na+g(nl,t,b)
    t = 10_8*t
  end do
  call show(ans)
  stop
contains
  recursive function f(l,t) result(r)
    integer(8), intent(in) :: l, t
    type(mint) :: r, s
    if (l.eq.0_8) then
      r = 0
      return
    end if
    if (mod(l,2_8).eq.0_8) then
      r = f(l/2_8,t)
      s = t
      r = r*(s**(l/2_8))+r
      return
    end if
    r = f(l-1_8,t)
    r = r*t+1
    return
  end function f
  recursive function g(l,t,b) result(r)
    integer(8), intent(in) :: l, t, b
    type(mint) :: r, s
    if (l.eq.0_8) then
      r = 0
      return
    end if
    if (mod(l,2_8).eq.0_8) then
      r = g(l/2_8,t,b)
      s = t
      r = r*(s**(l/2_8))+r+f(l/2_8,t)*(l/2_8)*b
      return
    end if
    r = g(l-1_8,t,b)
    s = b
    r = r*t+s*(l-1_8)
    return
  end function g
end program basics_in_education_and_learning

Measured memory_bytes: 256