This can be done with generating functions, as suggested by JMoravitz in a comment, and it's quite possible to do it with a pencil, though you'll probably want to use a calculator to do the arithmetic; I certainly did.
First, to understand the comment, note that $x_1$ and $x_2$ are each represented by the polynomial $$x^4+x^5+x^6+\dots+x^{29}.$$
This is because $4\leq x_1,x_2\leq29$.
Similarly, $x_3$ and $x_4$ are each represented by the polynomial $$x^{10}+x^{11}+\dots+x^{40}.$$ Finally, $x_5$ and $x_6$ are each represented by the polynomial $$1+x+x^2+\dots+x^{109}$$ Since the sum is to be $109$, neither $x_5$ nor $x_6$ can be more than $109$, and they must be $\geq0$.
To multiply these $6$ polynomials, we choose a term from each polynomial, multiply them together, and add up the products over all choices of terms. The coefficients in the polynomials are all $1$, so the coefficient of $x^n$ in the product, for some natural number $n$, is just the number of ways to pick one term from each polynomial such that the sum of their exponents is $n$. When $n=109$, this is just the solution to our problem. For example, the solution $x_=20,x_2=14,x_3=30,x_4=30,x_5=15,x_6=0$ corresponds to choosing the terms $x^{20},x^{14},x^{30},x^{30},x^{15},1$ from the polynomials, in order.
Now it's just a matter of figuring out the coefficient of $x^{109}$ without multiplying the polynomials.
I'll use the notation $[x^n]p(x)$ to mean the coefficient of $x^n$ in the formal power series $p(x)$. We want $$c=[x^{109}]\left(x^4+\cdots+x^{29}\right)^2
\left(x^{10}+\cdots+x^{40}\right)^2
\left(1+x+x^2+\cdots\right)^2
$$
Note that we don't need an upper bound on the $x_5$ and $x_6$. It doesn't matter if we include exponents $>109$ in the polynomial, because they won't contribute anything to the coefficient of $x^{109}$ in the product. As you'll see, this simplifies the calculation, because we have two fewer factor of the numerator this way.
Then, using the formula for a geometric series,$$
\begin{align}
c&=[x^{109}]\left(x^4-x^{30}\right)^2
\left(x^{10}-x^{41}\right)^2(1-x)^{-6}\\
&=[x^{81}]\left(1-x^{26}\right)^2
\left(1-x^{31}\right)^2
\sum_{n=0}^\infty\binom{-6}{n}(-x)^n\\
&=[x^{81}](1-2x^{26}+x^{52})(1-2x^{31}+x^{62})
\sum_{n=0}^{81}(-1)^n\binom{n+5}{5}(-x)^n\\
&=[x^{81}](1-2x^{26}-2x^{31}+x^{52}+4x^{57}+x^{62})
\sum_{n=0}^{81}\binom{n+5}{5}x^n\\
\end{align}$$
since we may ignore terms of degree $>81$.
We just need to pick out the terms in the product that result in a term of degree $81.$ We have $$
\binom{86}{5}-2\binom{60}5-2\binom{55}5+\binom{34}5+4\binom{29}5+\binom{24}5=17,741,536
$$
