Suppose that we have solved the first part by constructing the DP table for LCS. Now we can backtrack to obtain indices of common characters for both strings that form this LCS.
Let's define them as {a₁, a₂, ..., a_k} for the first string A, and {b₁, b₂, ..., b_k} for the second string B.
Of course, all unique shortest strings will contain these common characters, and the rest of A and B between these characters could be shuffled in all possible ways mantaining the relative order.

For example, consider the case LAILI and MAJNU where a₁ = b₁ = 2 (the A character).
Before these indices there are only L and M letters which can be ordered as LM or ML (2 combinations in total).
Next char will be A, and the rest (ILI and JNU) can be ordered in many ways such as ILIJNU, ILJNUI, ILJNIU etc.
There are 20 such combinations in total. We multiply all combinations together and obtain the answer 40.

Thus, we should calculate the number of shuffles for every substring between common LCS characters (a_i... a_i + 1) and (b_i... b_i + 1) — let's call them s_i and t_i — and multiply the results.
For calculating the number of shuffles we possibly can iterate through all of them using recursion since the problem statement says total number won't exceed 263.

But in fact, if we look deeper it's exactly the number of compositions of |s_i| as (|t_i| + 1) non-negative integer terms. You can write it down and see by yourself. The direct formula is and is explained here.