/**
 * @author Joseph Likar
 * last edited 2023-09-06
 */

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.File;
import java.io.IOException;
import java.math.BigInteger;
import java.nio.file.Files;
import java.util.*;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

import static java.math.BigInteger.*;

/**
 * The special cases when (m, r)q and r = 1 or 2
 */
enum SpecialQseq {
    NONE,
    ONE,
    TWO
}

public class Main {
    /**
     * This is a dictionary that contains locks to prevent recalculating a result
     */
    public static final HashMap<Integer, Set<Integer>> outstandingRequests = new HashMap<>();
    public static final HashMap<Integer, HashMap<Integer, QSequence>> cachedQs = new HashMap<>();
    /**
     * values calculated by either previous runs or other algorithms
     */
    public static final HashMap<Integer, BigInteger> knownAnswers = new HashMap<Integer, BigInteger>() {{
        // original OEIS value
        put(25, valueOf(663));
        // highest value calculated by my enumeration algo
        put(200, new BigInteger("627939054875"));
        // highest value calculated by js implementation of this algo
        put(500, new BigInteger("241616090679682707123"));
        // highest value calculated by this algo
        put(1000, new BigInteger("1832848313729278216858958831133"));
    }};
    public static int GOAL;
    public static BigInteger[] results;
    public static Integer completions = 0;

    /**
     * @param args provide maximum n to calculate
     */
    public static void main(String[] args) {
        ExecutorService reaper = Executors.newWorkStealingPool(12);

        final long start = System.currentTimeMillis();

        if (args.length > 0)
            GOAL = Integer.parseInt(args[0]);
        else
            GOAL = 25;

        // init lookup dict
        for (int i = 6; i <= GOAL; i++) {
            outstandingRequests.put(i, new HashSet<>());
            cachedQs.put(i, new HashMap<>());
        }

        final ArrayList<MyThread> tasks = new ArrayList<>(GOAL - 1);

        results = new BigInteger[GOAL + 1];

        for (int i = 0; i <= GOAL; i++) {
            results[i] = ZERO;
        }

        for (int usedNumbers = 2; usedNumbers <= GOAL; usedNumbers++) {
            MyThread newThred = new MyThread(usedNumbers);

            tasks.add(newThred);

            reaper.submit(newThred);
        }

        reaper.shutdown();
        try {
            reaper.awaitTermination(Long.MAX_VALUE, TimeUnit.MINUTES);
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
        System.out.println("I have been awakened");
        // sum up all results
        for (int i = tasks.size() - 1; i >= 0; i--) {
            if (tasks.get(i).completed) {
                BigInteger[] taskResults = tasks.remove(i).results;

                for (int j = 0; j <= GOAL; j++) {
                    results[j] = results[j].add(taskResults[j]);
                }
            }
        }

        for (int i = 0; i <= GOAL; i++) {
            System.out.println(i + " " + results[i]);
        }

        for (Map.Entry<Integer, BigInteger> entry : knownAnswers.entrySet()) {
            if (entry.getKey() < results.length && results[entry.getKey()].compareTo(entry.getValue()) != 0)
                throw new RuntimeException("You suck");
        }

        System.out.println(System.currentTimeMillis() - start);
    }
}

class MyThread implements Runnable {
    public final BigInteger[] results;
    /**
     * The number of numbers that need to be used and still result in a partition less than {@link Main#GOAL}
     */
    final int MY_N;
    public boolean completed = false;

    // init
    MyThread(int arg) {
        MY_N = arg;
        results = new BigInteger[Main.GOAL + 1];
        Arrays.fill(results, ZERO);
    }


    /**
     * Notes on how this works:
     * <p>
     * This method generates all the primitive families of partitions.
     * These families first require having a median that has a majority of entries.
     * In the event of an odd number of entries, then there must be at least one number above and below the median in the case where the median has (n + 1) / 2 entries
     */
    @Override
    public void run() {
        // any partition with fewer than this many entries as the median value will always fail
        final int baseMedianSize = (int) Math.ceil(MY_N / 2.0);
        // baseMedianSize case handled later
        for (int medianSize = baseMedianSize + 1; medianSize < MY_N; medianSize++) {
            if (Main.GOAL - 1 >= 3 * (MY_N - medianSize))
                countForFamily(MY_N, medianSize, 1, MY_N - medianSize);
            for (int medianValue = 2; medianValue * medianSize + (MY_N - medianSize) <= Main.GOAL; medianValue++) {
                for (int upperNumbers = 0; upperNumbers + medianSize <= MY_N && upperNumbers * (medianValue + 1) <= Main.GOAL - medianValue * medianSize - (MY_N - (medianSize + upperNumbers)) && Main.GOAL - 1 >= 3 * upperNumbers; upperNumbers++) {
                    countForFamily(MY_N, medianSize, medianValue, upperNumbers);
                }
            }
        }
        for (int medianValue = 1; medianValue * MY_N <= Main.GOAL; medianValue++) {
            results[medianValue * MY_N] = results[medianValue * MY_N].add(ONE);
        }
        // baseMedianSize case handled here
        if (MY_N % 2 == 1) {
            for (int medianValue = 2; medianValue * baseMedianSize + (MY_N - baseMedianSize) <= Main.GOAL; medianValue++) {
                for (int upperNumbers = 1; upperNumbers + baseMedianSize < MY_N; upperNumbers++) {
                    countForFamily(MY_N, baseMedianSize, medianValue, upperNumbers);
                }
            }
        }

        completed = true;

        synchronized (Main.completions) {
            Main.completions++;
            System.out.println(Main.completions + "   \r");
        }
    }

    /**
     * @param n Number of numbers to use
     * @param medianSize Number of numbers in the median
     * @param medianValue Value of the median
     * @param upperNumbers Number of numbers above the median
     */
    public void countForFamily(final int n, final int medianSize, final int medianValue, final int upperNumbers) {
        final int realMedianValue = medianSize * medianValue;
        final int bottomNumbers = n - (upperNumbers + medianSize);
        if (upperNumbers * (medianValue + 1) > Main.GOAL - realMedianValue - bottomNumbers)
            return;
        final int baseTopValue = upperNumbers * (medianValue + 1);

        final QSequence bottomQ = QSequence.getSequence(bottomNumbers + (medianValue - 1) - 1, bottomNumbers);
        final QSequence topQ = QSequence.getSequence(Main.GOAL - 1 - 2 * upperNumbers, upperNumbers);

        // convolve and add all valid Q coeff pairs
        for (int baseOffset = 0; baseOffset < bottomQ.sequenceLength && baseOffset <= bottomNumbers * (medianValue - 2) && baseTopValue + realMedianValue + bottomNumbers + baseOffset <= Main.GOAL; baseOffset++) {
            final BigInteger bottomVal = bottomQ.get(baseOffset);
            for (int topOffset = 0; topOffset < topQ.sequenceLength && baseTopValue + realMedianValue + bottomNumbers + baseOffset + topOffset <= Main.GOAL; topOffset++) {
                results[baseTopValue + realMedianValue + bottomNumbers + baseOffset + topOffset] = results[baseTopValue + realMedianValue + bottomNumbers + baseOffset + topOffset].add(bottomVal.multiply(topQ.get(topOffset)));
            }
        }
    }
}

class QSequence {
    private static final String Q_LOOKUP_DIR = "qbookup";
    public final int sequenceLength;
    public final SpecialQseq especial;
    private final BigInteger[] partialArray;

    private QSequence(BigInteger[] partialArray, int sequenceLength) {
        this(partialArray, sequenceLength, SpecialQseq.NONE);
    }

    private QSequence(BigInteger[] partialArray, int sequenceLength, SpecialQseq speciality) {
        this.partialArray = partialArray;
        this.sequenceLength = sequenceLength;
        this.especial = speciality;
    }

    public static QSequence generateFromFull(BigInteger[] fullArray) {
        return new QSequence(Arrays.copyOf(fullArray, fullArray.length % 2 == 0 ? fullArray.length / 2 : fullArray.length / 2 + 1), fullArray.length);
    }

    public static QSequence getSequence(final int m, int r) {
        synchronized (Main.cachedQs) {
            if (Main.cachedQs.containsKey(m) && Main.cachedQs.get(m).containsKey(r))
                return Main.cachedQs.get(m).get(r);
        }

        if (m < 0)
            return new QSequence(null, 1, SpecialQseq.ONE);

        if (m == r || r == 0)
            return new QSequence(null, 1, SpecialQseq.ONE);

        r = Math.min(r, m - r);

        if (r == 1) {
            return new QSequence(null, m, SpecialQseq.ONE);
        } else if (r == 2) {
            return new QSequence(null, 2 * m - 3, SpecialQseq.TWO);
        }

        // check if the recursive algorithm will be inexpensive, if it will be expensive, then just calculate directly
        if (!(new File(Q_LOOKUP_DIR + File.pathSeparator + (m - 1) + File.pathSeparator + (r - 1)).exists() && new File(Q_LOOKUP_DIR + File.pathSeparator + (m - 1) + File.pathSeparator + (Math.min(r, m - 1 - r))).exists()))
            return directCalculate(m, r);

        while (true) {
            synchronized (Main.outstandingRequests) {
                try {
                    if (Main.outstandingRequests.get(m).contains(r)) {
//                        System.out.println("Holding for " + m + " " + r);
                    } else {
                        Main.outstandingRequests.get(m).add(r);
                        break;
                    }
                } catch (Exception e) {
                    System.out.println("interrept");

                    throw new RuntimeException(e);
                }
            }
            try {
                Thread.sleep(10);
            } catch (InterruptedException e) {
                System.out.println("Insomniac");
                throw new RuntimeException(e);
            }
        }

        QSequence out = readFromDisk(m, r);

        if (out != null) {
            synchronized (Main.outstandingRequests) {
                Main.outstandingRequests.get(m).remove(r);
            }
            synchronized (Main.cachedQs) {
                Main.cachedQs.get(m).put(r, out);
            }
            return out;
        }

        out = getSequence(m - 1, r - 1).addOther(r, getSequence(m - 1, r)).writeToDisk(m, r);

        synchronized (Main.outstandingRequests) {
            Main.outstandingRequests.get(m).remove(r);
        }
        synchronized (Main.cachedQs) {
            Main.cachedQs.get(m).put(r, out);
        }
        return out;
    }

    public static QSequence directCalculate(int m, int r) {
        r = Math.min(r, m - r);

        if (m < 0)
            return new QSequence(null, 1, SpecialQseq.ONE);

        if (m == r || r == 0)
            return new QSequence(null, 1, SpecialQseq.ONE);

        r = Math.min(r, m - r);

        if (r == 1) {
            return new QSequence(null, m, SpecialQseq.ONE);
        } else if (r == 2) {
            return new QSequence(null, 2 * m - 3, SpecialQseq.TWO);
        }

        while (true) {
            synchronized (Main.outstandingRequests) {
                try {
                    if (!Main.outstandingRequests.get(m).contains(r)) {
                        Main.outstandingRequests.get(m).add(r);
                        break;
                    }
                } catch (Exception e) {
                    System.out.println("interrept");

                    throw new RuntimeException(e);
                }
            }
            try {
                Thread.sleep(10);
            } catch (InterruptedException e) {
                System.out.println("Insomniac");
                throw new RuntimeException(e);
            }
        }

        QSequence out = readFromDisk(m, r);

        if (out != null) {
            synchronized (Main.outstandingRequests) {
                Main.outstandingRequests.get(m).remove(r);
            }
            synchronized (Main.cachedQs) {
                Main.cachedQs.get(m).put(r, out);
            }
            return out;
        }

        BigInteger[] bigTop = new BigInteger[m + 1];
        Arrays.fill(bigTop, ZERO);
        bigTop[0] = ONE;
        bigTop[m] = ONE.negate();


        for (int em = m - 1; em >= m - r + 1; em--) {
            BigInteger[] bigCopy = bigTop;
            bigTop = new BigInteger[bigCopy.length + em];
            Arrays.fill(bigTop, bigCopy.length, bigTop.length, ZERO);
            System.arraycopy(bigCopy, 0, bigTop, 0, bigCopy.length);
            for (int i = 0; i < bigCopy.length; i++) {
                int windex = bigTop.length - bigCopy.length + i;
                bigTop[windex] = bigTop[windex].subtract(bigCopy[i]);
            }
        }

        BigInteger[] bigBot = new BigInteger[2];
        Arrays.fill(bigBot, ZERO);
        bigBot[0] = ONE;
        bigBot[1] = ONE.negate();

        for (int em = 2; em <= r; em++) {
            BigInteger[] bigCopy = bigBot;
            bigBot = new BigInteger[bigCopy.length + em];
            Arrays.fill(bigBot, bigCopy.length, bigBot.length, ZERO);
            System.arraycopy(bigCopy, 0, bigBot, 0, bigCopy.length);
            for (int i = 0; i < bigCopy.length; i++) {
                int windex = bigBot.length - bigCopy.length + i;
                bigBot[windex] = bigBot[windex].subtract(bigCopy[i]);
            }
        }

        out = QSequence.generateFromFull(QSequence.syntheticDivision(bigTop, bigBot)).writeToDisk(m, r);

        synchronized (Main.outstandingRequests) {
            Main.outstandingRequests.get(m).remove(r);
        }
        synchronized (Main.cachedQs) {
            Main.cachedQs.get(m).put(r, out);
        }
        return out;
    }

    private static BigInteger[] syntheticDivision(BigInteger[] bigTop, BigInteger[] bigBot) {
        BigInteger[] out = new BigInteger[bigTop.length - bigBot.length + 1];

        for (int i = bigTop.length - 1; i >= bigBot.length - 1; i--) {
            BigInteger newCoeff = bigTop[i].divide(bigBot[bigBot.length - 1]);
            out[i - bigBot.length + 1] = newCoeff;

            for (int j = 0; j < bigBot.length; j++) {
                bigTop[i - j] = bigTop[i - j].subtract(bigBot[bigBot.length - j - 1].multiply(newCoeff));
            }
        }

        return out;
    }

    public static QSequence readFromDisk(final int m, final int r) {
        final File infile = new File(Q_LOOKUP_DIR + File.pathSeparator + m + File.pathSeparator + r);

        if (!infile.exists()) {
            return null;
        }

        try {
            BigInteger[] bigOut = new BigInteger[(int) Math.ceil((r * (m - r) + 1) / 2.0)];
            bigOut[0] = ONE;
            bigOut[1] = ONE;
            bigOut[2] = valueOf(2);

            BufferedInputStream bis = new BufferedInputStream(Files.newInputStream(infile.toPath()));

            for (int i = 3; i < bigOut.length; i++) {
                int nextSize = bis.read() + 1;
                byte[] bia = new byte[nextSize];
                for (int j = 0; j < nextSize; j++) {
                    bia[j] = (byte) bis.read();
                }

                bigOut[i] = new BigInteger(bia);
            }

            bis.close();

            return new QSequence(bigOut, r * (m - r) + 1);
        } catch (IOException e) {
            System.out.println("failed to read");
            throw new RuntimeException(e);
        }
    }

    public QSequence writeToDisk(final int m, final int r) {
        final File outfile = new File(Q_LOOKUP_DIR + File.pathSeparator + m + File.pathSeparator + r);

        if (!outfile.getParentFile().exists()) {
            outfile.getParentFile().mkdirs();
        } else if (outfile.exists()) {
            return this;
        }

        try {
            outfile.createNewFile();

            BufferedOutputStream fos = new BufferedOutputStream(Files.newOutputStream(outfile.toPath()));

            for (int i = 3; i < partialArray.length; i++) {
                byte[] bao = partialArray[i].toByteArray();
                fos.write((byte) ((bao.length - 1) & 0xFF));
                fos.write(bao);
            }

            fos.flush();
            fos.close();

        } catch (IOException e) {
            System.out.println("Smthn went wrong in writing");
            throw new RuntimeException(e);
        }
        return this;
    }

    public QSequence addOther(int offset, QSequence other) {
        BigInteger[] outArr = new BigInteger[Math.max(offset + other.sequenceLength, sequenceLength)];

        for (int i = 0; i < offset; i++) {
            outArr[i] = get(i);
        }
        for (int i = offset; i < sequenceLength && i - offset < other.sequenceLength; i++) {
            outArr[i] = get(i).add(other.get(i - offset));
        }

        if (offset + other.sequenceLength < sequenceLength) {
            for (int i = offset + other.sequenceLength; i < sequenceLength; i++) {
                outArr[i] = get(i);
            }
        } else if (offset + other.sequenceLength > sequenceLength) {
            for (int i = sequenceLength - offset; i < other.sequenceLength; i++) {
                outArr[i + offset] = other.get(i);
            }
        }

        return generateFromFull(outArr);
    }

    public BigInteger get(int index) {
        if (index < 0 || index >= sequenceLength) {
            System.out.println("failed to get");
            throw new IndexOutOfBoundsException(index + " out of bounds for sequence of length " + sequenceLength);
        }

        switch (this.especial) {
            case NONE:
                return partialArray[Math.min(index, sequenceLength - index - 1)];
            case ONE:
                return ONE;
            case TWO:
                return valueOf(1 + Math.min(index / 2, (sequenceLength - index - 1) / 2));
            default:
                throw new IllegalStateException("This should never happen");
        }
    }
}