Storage device and operating method thereof

A memory device comprising:

• a memory cell array including memory cells;
• a program operation controller configured to perform a program operation on the memory cells to any one state among first to nth states, wherein n is a natural number greater than 1, distinguished according to their threshold voltages;
• a voltage generator configured to generate operating voltages respectively corresponding to the first to nth states in the program operation;
• a verify operation controller configured to verify whether the program operation performed on selected memory cells to a kth state, wherein k is a natural number less than n, has been completed, and count a number of over-programmed memory cells having a threshold voltage greater than a threshold voltage corresponding to the kth state among the selected memory cells;
• and
• an over-program manager configured to increase operating voltages respectively corresponding to (k+1)th to nth states to be greater than respectively corresponding default values according to the number of over-programmed memory cells.