Separability of rational relations in A∗×Nm by recognizable relations is decidable

Given a direct product of monoids M=A∗×Nm where A is finite and N is the additive monoid of nonnegative integers, the following problem is recursively decidable: given two rational subsets of M, does there exist a recognizable subset which includes one of the subsets and excludes the other.