;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam))
  #-swank (set-dispatch-macro-character #\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil (values) t))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS

(defun enum-quotients (n)
  "Given a positive integer N, floor(N/k) takes at most O(sqrt(N)) values for k
in {1, ..., N}. ENUM-QUOTIENTS returns the ascending vector of minimal integers
k that take `new' values compared to floor(N/(k-1)). Note that this vector
contains 1 and N+1.

Tips: Let A be the returned vector of length M+1 and an index i in {0, ..., M}
be given; then A[i]A[j] <= N iff j < M-i."
  (declare ((integer 0 #.most-positive-fixnum) n))
  (let ((k 1)
        (result (make-array (* 2 (isqrt n))
                            :element-type '(integer 0 #.most-positive-fixnum)
                            :adjustable t :fill-pointer 0)))
    (loop (vector-push-extend k result)
          (when (> k n)
            (return result))
          (setq k (+ 1 (floor n (floor n k)))))))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;; Body
;; TODO: use DEFTRANSFORM to optimize these functions when they are passed to a
;; inlined function
(defmacro define-mod-operations (&optional (divisor 1000000007))
  `(progn
     (defun mod* (&rest args)
        (reduce (lambda (x y) (mod (* x y) ,divisor)) args))

     (define-compiler-macro mod* (&rest args)
        (if (null args)
            1
            (reduce (lambda (x y) `(mod (* ,x ,y) ,',divisor)) args)))

     (defun mod+ (&rest args)
        (reduce (lambda (x y) (mod (+ x y) ,divisor)) args))

     (define-compiler-macro mod+ (&rest args)
        (if (null args)
            0
            (reduce (lambda (x y) `(mod (+ ,x ,y) ,',divisor)) args)))

     (define-modify-macro incfmod (delta divisor)
        (lambda (x y divisor) (mod (+ x y) divisor)))

     (define-modify-macro decfmod (delta divisor)
        (lambda (x y divisor) (mod (- x y) divisor)))))

(define-mod-operations)

(defun main ()
  (let* ((n (read))
         (k (read))
         (quots (coerce (enum-quotients n) '(simple-array uint32 (*))))
         (m+1 (length quots))
         (m (- m+1 1))
         (quots-size (make-array m :element-type 'uint32))
         (dp (make-array (list (+ k 1) m) :element-type 'uint32 :initial-element 0)))
    (declare (uint32 n m k)
             ((simple-array uint32 (*)) quots quots-size))
    (dotimes (i m) (setf (aref quots-size i) (- (aref quots (+ i 1)) (aref quots i))))
    (setf (aref dp 0 0) 1)
    (loop for y from 1 to k
          do ;; i = 0
             (let ((res 0))
               (declare (uint32 res))
               ;; (dbg y i (- m i))
               (dotimes (j m)
                 (incfmod res (mod* (aref dp (- y 1) j)
                                    (aref quots-size j))
                          +mod+))
               (setf (aref dp y 0) res))
             (loop for i from 1 below m
                   do (setf (aref dp y i)
                            (mod+ (aref dp y (- i 1))
                                  (- +mod+ (mod* (aref dp (- y 1) (- m i))
                                                 (aref quots-size (- m i))))))))
    ;; #>dp
    (let ((res 0))
      (declare (uint32 res))
      (dotimes (i m)
        (incfmod res (mod* (aref dp k i) (aref quots-size i))
                 +mod+))
      (println res))))

#-swank(main)


Measured memory_bytes: 48352