import { readFileSync } from "fs";

////////////////////////////////////////////////////////////////////////////////
// Application
////////////////////////////////////////////////////////////////////////////////
const P = 10 ** 9 + 7;
// eslint-disable-next-line @typescript-eslint/no-unused-vars
const [addP, subP, prodP, powP] = getModCalc(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;
}

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: 31004