import { readFileSync } from "fs";

////////////////////////////////////////////////////////////////////////////////
// Application
////////////////////////////////////////////////////////////////////////////////
/* number */
const P = 10 ** 9 + 7;
// eslint-disable-next-line @typescript-eslint/no-unused-vars
const [addP, subP, prodP, powP] = getNModCalc(P);
/* bigint */
// const P = 10n ** 9n + 7n;
// // eslint-disable-next-line @typescript-eslint/no-unused-vars
// const [addP, subP, prodP, powP] = getBModCalc(P);

const getPartitionNumber = (n: number): number => {
  type DicType = Map<number, number>;
  const dic: DicType = new Map<number, number>();
  range(4).forEach((i) => {
    dic.set(i, i < 3 ? 0 : 1);
  });
  const getValue = (n: number, dic: DicType) => {
    const rec = dic.get(n);
    return typeof rec !== "undefined"
      ? rec
      : (() => {
          const p = getPartitionNumber(n, dic);
          dic.set(n, p);
          return p;
        })();
  };
  const getPartitionNumber = (n: number, dic: DicType): number => {
    const rec = dic.get(n);
    return typeof rec !== "undefined"
      ? rec
      : addP(getValue(n - 1, dic), getValue(n - 3, dic));
  };
  return getPartitionNumber(n, dic);
};
const getAns = (S: number): string => getPartitionNumber(S).toString();

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

////////////////////////////////////////////////////////////////////////////////
// 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;
}

// eslint-disable-next-line @typescript-eslint/no-unused-vars
function getCin() {
  const inputs = readFileSync("/dev/stdin", "utf-8")
    .split("\n")
    .flatMap((l) => l.split(" "));
  let count = 0;
  const cin = () => inputs[count++];
  return tuple(
    cin,
    () => Number(cin()),
    () => BigInt(cin())
  );
}

// eslint-disable-next-line @typescript-eslint/no-unused-vars
function isNumber(x: unknown): x is number {
  return typeof x === "number";
}

// eslint-disable-next-line @typescript-eslint/no-unused-vars
function isBigint(x: unknown): x is bigint {
  return typeof x === "bigint";
}

// eslint-disable-next-line @typescript-eslint/no-unused-vars
function nMax(ns: number[]) {
  return ns.reduce((acc, n) => Math.max(acc, n));
}

// eslint-disable-next-line @typescript-eslint/no-unused-vars
function nMin(ns: number[]) {
  return ns.reduce((acc, n) => Math.min(acc, n));
}

// eslint-disable-next-line @typescript-eslint/no-unused-vars
function bMax(bs: bigint[]) {
  return bs.reduce((acc, b) => (acc >= b ? acc : b));
}

// eslint-disable-next-line @typescript-eslint/no-unused-vars
function bMin(bs: bigint[]) {
  return bs.reduce((acc, b) => (acc <= b ? acc : b));
}

// eslint-disable-next-line @typescript-eslint/no-unused-vars
function nAbs(n: number) {
  return Math.abs(n);
}

// eslint-disable-next-line @typescript-eslint/no-unused-vars
function bAbs(b: bigint) {
  return b >= 0n ? b : -b;
}

type BinaryOperation<T> = (x: T, y: T) => T;

// eslint-disable-next-line @typescript-eslint/no-unused-vars
function getNModCalc(n: number) {
  type CalcType = BinaryOperation<number>;
  const modAdd: CalcType = (x, y) => ((((x % n) + (y % n)) % n) + n) % n;
  const modSub: CalcType = (x, y) => ((((x % n) - (y % n)) % n) + n) % n;
  const modProd: CalcType = (x, y) => ((((x % n) * (y % n)) % n) + n) % n;
  const modPow: CalcType = (x, n) => {
    const isEvens = (() => {
      const isEvens: boolean[] = [];
      for (let tmpN = n; tmpN !== 1; tmpN = Math.floor(tmpN / 2))
        isEvens.push(tmpN % 2 === 0);
      return isEvens;
    })();
    return isEvens.reduceRight(
      (acc, b) => (b ? modProd(acc, acc) : modProd(x, modProd(acc, acc))),
      x
    );
  };
  return tuple(modAdd, modSub, modProd, modPow);
}

// eslint-disable-next-line @typescript-eslint/no-unused-vars
function getBModCalc(b: bigint) {
  type CalcType = BinaryOperation<bigint>;
  const modAdd: CalcType = (x, y) => ((((x % b) + (y % b)) % b) + b) % b;
  const modSub: CalcType = (x, y) => ((((x % b) - (y % b)) % b) + b) % b;
  const modProd: CalcType = (x, y) => ((((x % b) * (y % b)) % b) + b) % b;
  const modPow: CalcType = (x, b) => {
    const isEvens = (() => {
      const isEvens: boolean[] = [];
      for (let tmpN = b; tmpN !== 1n; tmpN /= 2n)
        isEvens.push(tmpN % 2n === 0n);
      return isEvens;
    })();
    return isEvens.reduceRight(
      (acc, b) => (b ? modProd(acc, acc) : modProd(x, modProd(acc, acc))),
      x
    );
  };
  return tuple(modAdd, modSub, modProd, modPow);
}


Measured memory_bytes: 31004