Two sequences A and B are called similar if they have the same length and have the following property: we can obtain two identical sequences by deleting at most two elements of A and at most two elements of B. (The elements deleted from A don't have to have the same indices as the elements deleted from B. The order of the remaining elements in each sequence has to be preserved.)
You are given ints N and bound.
Consider all the sequences with length N such that each element is an integer between 1 and bound, inclusive.
Compute the number of ordered pairs of such sequences that are similar.
Return this count modulo 1,000,000,009.