Interleaving Subsequences Stability

This problem is adapted from PA 2024 Runda 3 Splatanie ciągów.

We define the stability of an array as the length of the longest contiguous segment that is strictly monotonic (either increasing or decreasing). For example, the stability of the array \([8,6,1,3,5,7,4,2]\) is \(4\), because there exists a contiguous increasing segment \([1,3,5,7]\) and no strictly monotonic contiguous segment longer than that.

Let \(A \;\text{i}\; B\) denote any array produced by interleaving arrays \(A\) and \(B\) (i.e. the resulting array can be partitioned into two disjoint subsequences, one equal to \(A\) and the other equal to \(B\)). For instance, if \(A=[1,2,3]\) and \(B=[4,5]\), then valid interleavings include \([1,4,2,5,3]\), \([4,5,1,2,3]\) and \([4,1,5,2,3]\); however, \([1,2,3,4,3]\) or \([1,2,3,5,4]\) are not possible.

Define \(f(A,B)\) as the minimum stability among all arrays formed by interleaving \(A\) and \(B\).
You are given an array \(A\) of length \(n\) and an array \(B\) of length \(m\). Let \(A'\) be any non-empty contiguous subarray of \(A\) and \(B'\) any non-empty contiguous subarray of \(B\). For every integer \(x\) in the interval \([1, n+m]\), compute the number of pairs \((A',B')\) such that \(f(A',B')=x\). Since the answer can be large, output it modulo \(10^9+7\).

Note: In this problem, an interleaving refers to a merging of two arrays that preserves the internal order of the elements from each array.

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1\leq n,m\leq 10)\) representing the lengths of arrays \(A\) and \(B\) respectively (note: the bounds are small to allow a brute force solution).
The second line contains \(n\) integers representing the array \(A\).
The third line contains \(m\) integers representing the array \(B\).

outputFormat

Output a single line containing \(n+m\) integers. The \(x\)-th integer (for \(1 \le x \le n+m\)) should equal the number of pairs \((A',B')\) such that \(f(A',B')=x\), taken modulo \(10^9+7\).

sample

2 2
1 2
3 4

0 9 0 0