MODULE combinationMod
!ref
!https://www.hamayanhamayan.com/entry/2018/06/06/210256

!!!!!  procedure list  !!!!!
!combination( n,k )
!  O(N*logModulus) ==> O(1)
!combinationN( n,k )
!  O(N*logModulus) ==> O( k )
!  for larger N
!initialize( setSize!optional )
!inv( x )
!pow( x,n )
!modSum( a,b )   => .plus.
!modSub( a,b )   => .minus.
!modMulti( a,b ) => .times.
      implicit none
      public
      integer(16),parameter :: modulus = 10**9 + 7
        !sz : max limit of NandK(arg of comb),default is 10**6
      private :: sz, factorial, reciproF
      integer(16) :: sz 
      integer(16),allocatable :: factorial(:),reciproF(:)

      interface operator (.plus.)
        module procedure :: modSum
      end interface
      interface operator (.minus.)
        module procedure :: modSub
      end interface
      interface operator (.times.)
        module procedure :: modMulti
      end interface

      contains
      pure function combination( n,k ) result( ans )
        implicit none
        integer(16),intent(in) :: n,k
        integer(16) :: ans, a, b, c, bc
        
        a = factorial(n)
        b = reciproF(n-k)
        c = reciproF(k)
        
        bc = b .times. c
        
        ans = a .times. bc
      end function combination


      pure function combinationN( n,k ) result( ans )
        implicit none
        integer(16),intent(in) :: n,k
        integer(16) :: ans,denominator,numerator !(nu/de)
        integer(16) :: i,nn
        
        nn = n
        numerator = 1
        do i = 1,k
          numerator = numerator .times. nn
          nn = nn - 1
        end do
        denominator = reciproF(k)
        ans = numerator .times. denominator
      end function combinationN


      subroutine initialize( setSize )
        implicit none
        integer(16),intent(in),optional :: setSize
        integer(16) :: i
        
        sz = 10**6
        if(present(setSize)) sz = setSize
        allocate( factorial(0:sz),reciproF(0:sz) )
        
        !calc factrial
        factorial(0) = 1
        do i = 1,sz
          factorial(i) = factorial(i-1) .times. i
        end do
        !calc reciprocal of factorial
        do i = 0,sz
          reciproF(i) = inv( factorial(i) )
        end do
      end subroutine initialize


      pure function inv( x ) result( ans )
        implicit none
        integer(16),intent(in) :: x
        integer(16) :: ans,i
        
        ans = pow( x,modulus-2 )
      end function inv


!calc x**n (mod)
      pure function pow( x,n ) result( ans )
        implicit none
        integer(16),intent(in) :: x,n
        integer(16) :: ans, k, y
        
        ans = 1
        k = n
        y = x
        do while( k/=0 )
          if( iand(k,1)==1 )then
            ans = ans .times. y
          end if
          y = y .times. y
          k = k / 2
        end do
      end function pow


      !operators
      pure function modSum( a,b ) result( res )
        implicit none
        integer(16),intent(in) :: a,b
        integer(16) :: res
        
        res = mod( a+b,modulus )
      end function
      pure function modSub( a,b ) result( res )
        implicit none
        integer(16),intent(in) :: a,b
        integer(16) :: res
        
        res = mod( a-b+modulus,modulus )
      end function
      pure function modMulti( a,b ) result( res )
        implicit none
        integer(16),intent(in) :: a,b
        integer(16) :: res
        
        res = mod( a*b,modulus )
      end function
      
      END MODULE combinationMod



      PROGRAM bouquet
      use combinationMod
      IMPLICIT NONE
      integer(16) :: ans,n,a,b
      integer(16) :: subA,subB
      
      read*,n,a,b
      
      ans = pow(2_16,n) - 1
      
      call initialize()
      
      subA = combinationN(n,a)
      subB = combinationN(n,b)
      ans = ans .minus. subA .minus. subB
      
      print*,ans
      
      
      END PROGRAM

Measured memory_bytes: 31528