Here is a recursive algorithm of complexity $O(n^2 m)$ where there are $n$ symbols and the largest set of values replacing a symbol is $\lbrace 0, 1, ..., m-1 \rbrace$.

Let $m_i$ be the number of values replacing the $i$th symbol, $0\le i \lt n$. Without loss of generality, assume the $m_i$ are nondecreasing.

Define $f(a,b)$ be the number of distinct ways of ordering and replacing the last $a$ symbols so that each value is at least $b$. We want to compute $f(n,0)$. 

If $m_0 = 0$ then $f(n,0)=0$ since there are no possible replacements. Otherwise, if we choose the number of $0$s to be z, then there are $n \choose z$ ways to place the $0$s, and there are $f(n-z,1)$ ways to choose the other symbols. So, $f(n,0) = \sum_z {n \choose z} f(n-z,1)$. More generally, if $m_{n-a} \le b$ then $f(a,b)=0$, otherwise

$$f(a,b) = \sum_{z=0}^a {a\choose z} f(a-z,b+1).$$

At the base of the recursion, $f(0,b)=1$.

Here is some Mathematica code which implements this with some examples

    Clear[rec];
    rec[a_, b_, mVec_] := rec[a, b, mVec] = 
       If[a == 0, 1, 
          If[mVec[[Length[mVec] - a + 1]] <= b, 0, 
             Sum[Binomial[a, z] rec[a - z, b + 1, mVec], {z, 0, a}]
            ]
         ]
    rec[3, 0, {3, 3, 3}]
       27
    rec[3, 0, {1, 2, 3}]
       16
    rec[4, 0, {1, 2, 3, 4}]
       125
    Timing[rec[20, 0, {12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50}]]
    {0.031, 4822195074448408017997909570093056}
That last value is $2^{40}\times 3 \times 13^{19} = 12\times(52)^{19}$. There is a nice factorization when the $m_i$ are in an arithmetic progression which follows from the recursion. What is the origin of this problem?