As High Efficiency Video Coding (HEVC) is a worldwide popular video coding standard, the steganography of HEVC videos has gained more and more attention. Prediction Unit (PU) is one of the most important innovative modules of HEVC, thus PU partition mode based steganography is becoming a novel branch of HEVC steganography. However, the embedding capacity of this kind of steganography is limited by the types of PU partition modes. To solve the problem, modified Exploiting Modification Direction (EMD) coded PU partition modes based steganography is proposed in this paper, which can hide a secret digit in a ( [[EQUATION]] )-ary notational system in a pair of PU partition modes and thus enlarging the capacity. Furthermore, two mapping patterns for PU partition modes are analyzed and the one that performs the better is selected as the final mapping pattern. Firstly, 8×8 and 16×16 sized PU partition modes are recorded according to the optimal mapping pattern in the video encoding process. Then PU partition modes are modified by using the proposed method to satisfy the requirement of secret information. Finally, the stego video can be obtained by re-encoding the video with the modified PU partition modes. Experimental results show that the embedding capacity can be significantly enlarged, and compared with the state-of-the-art work, the proposed method has much larger capacity while keeping high visual quality.