안녕하삼. 삼과 죽음 강의를 듣다가 삼의 저주에 걸려버렸삼.
이 저주를 풀기 위해서는 특정 자릿수 k가 주어졌을 때 3개의 조건을 만족하는 수의 개수를 출력해야하삼.
조건
- 특정 자릿수 k 자릿수를 만족해야하삼.
(ex. k가 3이라면 124, 341, 551는 세자릿수가 맞지만, 025와 2156은 세자릿수가 아니므로 인정되지 않삼.
즉, 0을 제외한 모든 숫자는 0으로 시작할 수 없삼. 0은 한자릿수이삼.)
- 만들어진 숫자에 3이 들어가면 안되삼.
(ex. 223 은 3이 들어가 있기에 불가능하삼.)
- 만들어진 최종 숫자가 3의 배수가 아니어야하삼.
(ex. 123은 3의 배수이기에 불가능하삼.)
위 조건을 만족하는 수의 개수를 찾아서 얼른 이 저주에서 나를 구해주삼!
입력으로 특정 자릿수를 나타내는 자연수 k (k < 18)가 주어지삼.
자릿수가 k인 수 중에 3이 안들어가고, 3의 배수가 아닌 수가 몇개인지를 출력해삼.