Count and Enumerate 1-D Walk Sequences with Fixed Sum

We are given a sequence \(a_1, a_2, \dots, a_n\) with \(a_1 = 0\) and for every \(1 \le i < n\), \(|a_i - a_{i+1}| = 1\). Define the sum \(s = \sum_{i=1}^{n} a_i = a_1 + a_2 + \cdots + a_n\).

Given the length \(n\) and the target sum \(s\), your task is to:

• Compute the total number of sequences satisfying the condition, modulo \(2^{64}\).
• Output 100 valid sequences (if there are fewer than 100, output all of them). Each sequence is printed on a new line with the \(n\) numbers separated by a single space.

Note: The modulo \(2^{64}\) means that the arithmetic is performed under the 64-bit unsigned integer modulus.

inputFormat

The input consists of two integers (n) and (s) separated by whitespace. (n) is the length of the sequence and (s) is the target sum of the sequence.

outputFormat

On the first line, output the total count of valid sequences modulo (2^{64}). In the following lines, output each valid sequence on a separate line. Each sequence should consist of (n) integers separated by a single space. If there are more than 100 valid sequences, only output the first 100.

sample

3 1

2
0 1 0
0 -1 0