다음과 같이 콜라츠(Collatz) 수열을 변형시킨 정수 수열을 만듭니다. $a_1$부터 시작합니다:

$a_n$가 $3$으로 나눠지면, $a_{n+1} = \, \,\, \frac {a_n} 3 \quad$입니다. 아래로 크게 한 단계 내려간다는 의미로 "D"로 표기합니다.

$a_n$을 $3$으로 나눈 나머지가 $1$이면, $a_{n+1} = \frac {4 a_n+2} 3 \, \,$입니다. 위로 올라간다는 의미로 "U"로 표기합니다.

$a_n$을 $3$으로 나눈 나머지가 $2$이면, $a_{n+1} = \frac {2 a_n -1} 3 \, \,$입니다. 아래로 작게 한 단계 내려간다는 의미로 "d"로 표기합니다.

어떤 항의 값 $a_n = 1$이면 수열은 종료됩니다.

어떤 자연수도 각 단계의 순서로 나열할 수 있습니다.
예로, $a_1=231$일 때, 수열 $\{a_n\}=\{231,77,51,17,11,7,10,14,9,3,1\}$은 단계 "DdDddUUdDD"와 대응됩니다.

물론, 같은 단계 "DdDddUUdDD...."로 시작하는 다른 수열도 존재합니다.
예로, $a_1=1004064$일 때, 단계는 DdDddUUdDDDdUDUUUdDdUUDDDUdDD입니다.
사실, $1004064$은 단계 DdDddUUdDD로 시작하는 가장 작은 $a_1 > 10^6$입니다.

단계 "UDDDUdddDDUDDddDdDddDDUDDdUUDd"로 시작하는 $a_1 > 10^{15}$의 최솟값은 얼마입니까?