Description

There is a sequence $a_1, a_2, \cdots, a_n$, where $a_{1} = 0$, and for any term $a_i$ it holds that $|a_i - a_{i+1}| = 1$ ($1 \le i < n$). Let $s = \sum_{i = 1}^n a_i = a_{1} + a_{2} + \cdots + a_{n}$ denote the sum of the first $n$ terms.

Given the length $n$ and the sum $s$ of the first $n$ terms, do the following:

• Output the total number of sequences that satisfy the conditions, modulo $2^{64}$.
• Output up to $100$ sequences that satisfy the conditions (if fewer than $100$ exist, output all of them).

Input Format

The input contains a single line with two integers, the sequence length $n$ and the sum $s$.

Output Format

This problem uses a Special Judge.

On the first line, output a single integer $t$, the total number of valid sequences modulo $2^{64}$.

Then output several lines, each containing $n$ integers, describing one valid sequence.

4 0

2
0 -1 0 1
0 1 0 -1

Hint

• Constraints

  For all testdata, it is guaranteed that $1 \le n \le 100$, $-2^{63} \le s < 2^{63}$.

• Notes

  Special Judge provider:

  user/230249

Translated by ChatGPT 5