Complexity for the toys solution is not n, as you call clojure sort in your code

Updated

case and compare might help you make the cond faster and/or more readable. Also, clojure.core already has memoize. And finally, rem is a simpler (slightly faster) form of mod, when you don't care about negative numbers:

(defn step-perms [n]
  (let [memoed
         (memoize
           (fn f [n]
            (case (compare n 3)
              -1 n
              0 4
              (+ (f (dec n))
                 (f (- n 2))
                 (f (- n 3))))))]
    (rem (memoed n) 10000000007)))

(defn step-perms [n]
  (case (compare n 3)
    -1 n
    0 4
    (let [buf (int-array (inc n))
          _ (aset buf 1 1)
          _ (aset buf 2 2)
          _ (aset buf 3 4)]
      (loop [i 4]
        (if (> i n)
          (aget buf n)
          (do
            (aset buf i
              (rem
                (+ (aget buf (dec i))
                   (aget buf (- i 2))
                   (aget buf (- i 3)))
                10000000007))
            (recur (inc i)))))))