#WA想定 N=int(input()) assert 1<=N<=10**9