We conducted a molecular dynamics simulation of the binary nucleation in the vapor mixture consisting of water and a small amount of sulfuric acid and investigated the microscopic process in relation to the structure of the hydrate (binary cluster composed of sulfuric acid and water). It was observed that the nucleation rate increased with the concentration of sulfuric acid. It was found that the formation of the hydrate is stable as long as its size is small enough, and the hydrate growth by coagulation played a major part in the enhanced nucleation. The rate of coagulation became larger by the uptake of more sulfuric acid in the hydrate, while it was suppressed with increasing the hydration number. We found that such features came from the structure of the small hydrate which was a multishell structure composed of an inner shell of sulfuric acid and diffused outer shell of water.