[고등부] 2025 KOI 1차대회 대비 모의고사 (1주차)

요리 경연대회에 나온 유명 셰프 에두워두는 물코기 요리가 하고 싶어졌다.

대회에 준비된 물코기는 총 N마리로 각 i번째 물코기는 길이 A_icm이며, B_i색을 띄고 있다.

심사위원 중 한 명은 하나의 요리에 이븐(even)한(크기차이가 크지않은) 길이의 물코기들만 사용하는 것을 중요하게 생각하기에 각 물코기의 길이의 차이가 두 배 이상 나면 안된다.

즉, X물코기의 길이가 3cm이고, Y물코기의 길이가 6cm라면 두 물코기는 함께 요리에 사용될 수 없다.

에두워두 셰프는 물코기의 색을 다양한 조합으로 사용하여 요리를 하고 싶어졌지만, 물코기의 수가 많아짐에 따라 얼마나 많은 조합이 가능한지 계산하기 힘들어졌다.

요리할 수 있는 색의 조합의 수를 계산하는 프로그램을 작성하시오.