[BOJ] 백준 28294 프랙탈 Python

import sys
input = sys.stdin.readline

N, a  = map(int,input().split())
##거듭제곱을 한 결과의 modular 연산에 유용한 툴.
특히, prime number로 나누는 경우## 
def power(a, b):
    if b == 0:
        return 1
    elif b == 1:
        return a
    
    tmp = power(a, b//2)
    if b%2 == 0:
        return tmp*tmp % 1_000_000_007
    return tmp*tmp*a % 1_000_000_007


result = (N * (N-1) *(power(N,a) - power(N-1,a)) 
+ power(N-1,a) * N) % 1_000_000_007


print(result)

항상 어떻게든 규칙성을 찾고 풀려는 기질이 다분하게 보이는 상황이라서 조금 웃기네요.
다른 좋은 방법도 많이 있을 것 같습니다.
코드로 풀어 쓸 것을 그냥 합공식으로 다 때려서 계산해버린 느낌이네요 ㅋㅋ.

Hint: 프랙탈의 둘레 길이는 각각의 step에서 이하와 같이 주어집니다.

Step 1: N^a x (N-1),
Step 2: N^{a-1} x (N-1)^2
Step a: N x (N-1)^a
Final Step: N x (N-1)^a로 주어진다.
Step 1~a의 합: N x (N-1)x (power(N,a)- power(N-1,a))이 되는 것은
N x (N-1)을 공통 인수로 취한 뒤, 등비수열 합공식을 사용하면 알아낼 수 있습니다.
Final step: power(N-1,a) x N