I was preparing some problems for a college contest from the past few weeks and came up with this problem idea.

Given N words consisting of either lowercase English letters or a special character '#'. 
Find the expected number of nodes in the trie after a trie is constructed replacing all the special character('#') in the words uniformly randomly with any letter between 'a' to 'z'. 

I want to know if there exists any polynomial-time solution for this problem.

Thanks.