Case 1: 6
Case 2: 318384
Case 3: 45