Two sorted sequences, lengths 11 and 8, are given: (a, b, c, d, e, f, g, h, i, j, k)(a,b,c,d,e,f,g,h,i,j,k) and (1, 2, 3, 4, 5, 6, 7, 8)(1,2,3,4,5,6,7,8).

We want to interleave them into one sequence of length 19 such that:

• The letters a...ka...k remain in relative order, and
• The numbers 1...81...8 remain in relative order.

For example a, b, c, 1, 2, d, 3, e, 4, 5, f, g, h, 6, i, 7, 8, j, ka,b,c,1,2,d,3,e,4,5,f,g,h,6,i,7,8,j,k is a valid interleaving.

How many valid interleavings exist?