• 먼저 빨간색만 색칠해보자. 색칠 방법은 N! 이다.
• 이제 여기에 파란색을 색칠해보자. 각각의 열에 들어갈 행 번호가 모두 달라야 하고, 답이 될수 없는 번호가 하나씩 있다. n개의 원소가 모두 원래 위치에 있지 않게 배열하는 방법의 수와 같은 문제이므로 교란순열 (Derangement)로 풀수 있다
  • 잘 안떠오르면 각 열들을 파란색이 색칠된 행의 번호순으로 정렬시켜놓고 생각하면 된다
• 구해야 하는 답은 N!*D(N). 시간복잡도는 O(n)이다

"""Solution code for "BOJ 14578. 영훈이의 색칠공부".

- Problem link: https://www.acmicpc.net/problem/14578
- Solution link: http://www.teferi.net/ps/problems/boj/14578

Tags: [combinatoric]
"""

from teflib import combinatorics

MOD = 1_000_000_007


def main():
    N = int(input())
    print(
        combinatorics.factorial(N, MOD)
        * combinatorics.derangement(N, MOD)
        % MOD
    )


if __name__ == '__main__':
    main()

• Dependency
  • teflib.combinatorics.factorial
  • teflib.combinatorics.derangement