[중등 극심화] 정사각형 격자를 서로 인접하지 않게 색칠하는 방법의 수

가로와 세로의 길이가 각각 $4$인 정사각형 격자가 있다. 이 격자의 $16$개의 단위정사각형 중 몇 개를 색칠하되, 변을 공유하는 두 단위정사각형을 동시에 색칠하지 않도록 한다. 이때 색칠하는 방법의 수를 1000으로 나눈 나머지를 구하시오. (단, 어느 단위정사각형도 색칠하지 않는 경우를 포함한다.)