import { readFileSync } from "fs";

/**
 * Application
 */
const P = 10n ** 9n + 7n;
// eslint-disable-next-line @typescript-eslint/no-unused-vars
const [addP, subP, prodP, powP] = getModCalc(P);
const getPartitionNumber = (n: bigint): bigint => {
  const dic = new Map<bigint, bigint>();
  range(3)
    .map((i) => BigInt(i))
    .forEach((i) => {
      dic.set(i, 0n);
    });
  const getPartitionNumber = (n: bigint): bigint => {
    const rec = dic.get(n);
    return typeof rec !== "undefined"
      ? rec
      : 1n +
          range(max(0n, n - 3n))
            .map((i) => BigInt(i) + 3n)
            .map((i) => {
              const rec = dic.get(n - i);
              return typeof rec !== "undefined"
                ? rec
                : (() => {
                    const p = getPartitionNumber(n - i);
                    dic.set(n - i, p);
                    return p;
                  })();
            })
            .reduce((acc, p) => addP(acc, p), 0n);
  };
  return getPartitionNumber(n);
};

const getAns = (S: bigint): string => getPartitionNumber(S).toString();
{
  // eslint-disable-next-line @typescript-eslint/no-unused-vars
  const [cin, nCin, bCin] = getCin();
  const S = bCin();
  const ans = getAns(S);
  console.log(ans);
}

/**
 * Library
 */
// eslint-disable-next-line @typescript-eslint/no-unused-vars
function range(n: number | bigint) {
  return Array.from(Array(Number(n)), (_, i) => i);
}
function tuple<T extends unknown[]>(...ts: T) {
  return ts;
}
function getCin() {
  const inputs = readFileSync("/dev/stdin", "utf-8").split(/[\n|\s]+/);
  let count = 0;
  const cin = () => inputs[count++];
  return tuple(
    cin,
    () => Number(cin()),
    () => BigInt(cin())
  );
}
function isNumber(x: unknown): x is number {
  return typeof x === "number";
}
function isBigint(x: unknown): x is bigint {
  return typeof x === "bigint";
}
type NumberOrBigintOrElse<T> = number | bigint extends T
  ? undefined
  : T extends number
  ? number
  : T extends bigint
  ? bigint
  : undefined;
// eslint-disable-next-line @typescript-eslint/no-unused-vars
function max<T extends number | bigint>(...ts: T[]) {
  return (ts.length === 0
    ? undefined
    : isNumber(ts[0])
    ? Math.max(...(ts as number[]))
    : (ts as bigint[]).reduce((acc, t) =>
        acc >= t ? acc : t
      )) as NumberOrBigintOrElse<T>;
}
// eslint-disable-next-line @typescript-eslint/no-unused-vars
function min<T extends number | bigint>(...ts: T[]) {
  return (ts.length === 0
    ? undefined
    : isNumber(ts[0])
    ? Math.min(...(ts as number[]))
    : (ts as bigint[]).reduce((acc, t) =>
        acc <= t ? acc : t
      )) as NumberOrBigintOrElse<T>;
}
// eslint-disable-next-line @typescript-eslint/no-unused-vars
function abs<T extends number | bigint>(t: T) {
  return (isNumber(t)
    ? Math.abs(t)
    : isBigint(t)
    ? t >= 0n
      ? t
      : -t
    : undefined) as NumberOrBigintOrElse<T>;
}
type BinaryOperation<T> = (x: T, y: T) => T;
// eslint-disable-next-line @typescript-eslint/no-unused-vars
function getModCalc<T extends number | bigint>(n: T) {
  type CalcType = BinaryOperation<NumberOrBigintOrElse<T>>;
  const modAdd = ((x, y) =>
    isNumber(x) && isNumber(y) && isNumber(n)
      ? ((((x % n) + (y % n)) % n) + n) % n
      : isBigint(x) && isBigint(y) && isBigint(n)
      ? ((((x % n) + (y % n)) % n) + n) % n
      : undefined) as CalcType;
  const modSub = ((x, y) =>
    isNumber(x) && isNumber(y) && isNumber(n)
      ? ((((x % n) - (y % n)) % n) + n) % n
      : isBigint(x) && isBigint(y) && isBigint(n)
      ? ((((x % n) - (y % n)) % n) + n) % n
      : undefined) as CalcType;
  const modProd = ((x, y) =>
    isNumber(x) && isNumber(y) && isNumber(n)
      ? ((((x % n) * (y % n)) % n) + n) % n
      : isBigint(x) && isBigint(y) && isBigint(n)
      ? ((((x % n) * (y % n)) % n) + n) % n
      : undefined) as CalcType;
  const modPow: CalcType = (x, n) => {
    const isEvens =
      isNumber(x) && isNumber(n)
        ? ((x: number, n: number) => {
            let tmpN = n;
            const isEvens: boolean[] = [];
            while (tmpN !== 1) {
              isEvens.push(tmpN % 2 === 0);
              tmpN = Math.floor(tmpN / 2);
            }
            return isEvens;
          })(x, n)
        : isBigint(x) && isBigint(n)
        ? ((x: bigint, n: bigint) => {
            let tmpN = n;
            const isEvens: boolean[] = [];
            while (tmpN !== 1n) {
              isEvens.push(tmpN % 2n === 0n);
              tmpN /= 2n;
            }
            return isEvens;
          })(x, n)
        : undefined;
    return (typeof isEvens !== "undefined"
      ? isEvens.reduceRight((acc, b) => {
          const tmp = modProd(acc, acc);
          return b ? tmp : modProd(x, tmp);
        }, x)
      : undefined) as NumberOrBigintOrElse<T>;
  };
  return tuple(modAdd, modSub, modProd, modPow);
}


Measured memory_bytes: 91224