MOD = 1000000000 K = 92 MASK = (1 << 30) - 1 DECAY = [ [0, -1, -1, -1, -1, -1], [71, 90, 0, 19, 2, -1], [1, -1, -1, -1, -1, -1], [31, 19, 2, -1, -1, -1], [3, -1, -1, -1, -1, -1], [4, -1, -1, -1, -1, -1], [5, -1, -1, -1, -1, -1], [6, -1, -1, -1, -1, -1], [7, -1, -1, -1, -1, -1], [8, -1, -1, -1, -1, -1], [9, -1, -1, -1, -1, -1], [60, 10, -1, -1, -1, -1], [11, -1, -1, -1, -1, -1], [12, -1, -1, -1, -1, -1], [66, 13, -1, -1, -1, -1], [14, -1, -1, -1, -1, -1], [15, -1, -1, -1, -1, -1], [16, -1, -1, -1, -1, -1], [17, -1, -1, -1, -1, -1], [18, -1, -1, -1, -1, -1], [66, 90, 0, 19, 26, -1], [20, -1, -1, -1, -1, -1], [21, -1, -1, -1, -1, -1], [22, -1, -1, -1, -1, -1], [23, 13, -1, -1, -1, -1], [24, -1, -1, -1, -1, -1], [25, -1, -1, -1, -1, -1], [29, 26, -1, -1, -1, -1], [27, -1, -1, -1, -1, -1], [28, -1, -1, -1, -1, -1], [62, 19, 88, 0, 19, 29], [66, 30, -1, -1, -1, -1], [31, 10, -1, -1, -1, -1], [32, -1, -1, -1, -1, -1], [33, -1, -1, -1, -1, -1], [34, -1, -1, -1, -1, -1], [35, -1, -1, -1, -1, -1], [36, -1, -1, -1, -1, -1], [37, 91, -1, -1, -1, -1], [38, 0, 19, 42, -1, -1], [67, 39, -1, -1, -1, -1], [40, -1, -1, -1, -1, -1], [41, -1, -1, -1, -1, -1], [62, 19, 42, -1, -1, -1], [66, 43, -1, -1, -1, -1], [44, -1, -1, -1, -1, -1], [45, -1, -1, -1, -1, -1], [46, -1, -1, -1, -1, -1], [47, -1, -1, -1, -1, -1], [48, -1, -1, -1, -1, -1], [60, 49, -1, -1, -1, -1], [62, 19, 50, -1, -1, -1], [66, 51, -1, -1, -1, -1], [52, -1, -1, -1, -1, -1], [53, -1, -1, -1, -1, -1], [54, -1, -1, -1, -1, -1], [55, -1, -1, -1, -1, -1], [56, 0, 19, 26, -1, -1], [57, -1, -1, -1, -1, -1], [58, -1, -1, -1, -1, -1], [59, -1, -1, -1, -1, -1], [60, 19, 29, -1, -1, -1], [61, -1, -1, -1, -1, -1], [62, 19, 26, -1, -1, -1], [66, 63, -1, -1, -1, -1], [64, -1, -1, -1, -1, -1], [65, -1, -1, -1, -1, -1], [66, 60, -1, -1, -1, -1], [67, 19, 26, -1, -1, -1], [68, -1, -1, -1, -1, -1], [69, -1, -1, -1, -1, -1], [70, -1, -1, -1, -1, -1], [71, 90, 0, 19, 73, -1], [72, -1, -1, -1, -1, -1], [31, 19, 73, -1, -1, -1], [74, -1, -1, -1, -1, -1], [75, -1, -1, -1, -1, -1], [76, -1, -1, -1, -1, -1], [77, -1, -1, -1, -1, -1], [78, -1, -1, -1, -1, -1], [79, -1, -1, -1, -1, -1], [80, -1, -1, -1, -1, -1], [60, 81, -1, -1, -1, -1], [82, -1, -1, -1, -1, -1], [83, -1, -1, -1, -1, -1], [66, 84, -1, -1, -1, -1], [85, -1, -1, -1, -1, -1], [86, -1, -1, -1, -1, -1], [87, -1, -1, -1, -1, -1], [88, -1, -1, -1, -1, -1], [89, -1, -1, -1, -1, -1], [90, -1, -1, -1, -1, -1] ] DECAY_COUNT = [ 1, 5, 1, 3, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 5, 1, 1, 1, 2, 1, 1, 2, 1, 1, 6, 2, 2, 1, 1, 1, 1, 1, 2, 4, 2, 1, 1, 3, 2, 1, 1, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 4, 1, 1, 1, 3, 1, 3, 2, 1, 1, 2, 3, 1, 1, 1, 5, 1, 3, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1 ] ELEMENT_STRINGS = [ "22", "13112221133211322112211213322112", "312211322212221121123222112", "111312211312113221133211322112211213322112", "1321132122211322212221121123222112", "3113112211322112211213322112", "111312212221121123222112", "132112211213322112", "31121123222112", "111213322112", "123222112", "3113322112", "1113222112", "1322112", "311311222112", "1113122112", "132112", "3112", "1112", "12", "3113112221133112", "11131221131112", "13211312", "31132", "111311222112", "13122112", "32112", "11133112", "131112", "312", "13221133122211332", "31131122211311122113222", "11131221131211322113322112", "13211321222113222112", "3113112211322112", "11131221222112", "1321122112", "3112112", "1112133", "12322211331222113112211", "1113122113322113111221131221", "13211322211312113211", "311322113212221", "132211331222113112211", "311311222113111221131221", "111312211312113211", "132113212221", "3113112211", "11131221", "13211", "3112221", "1322113312211", "311311222113111221", "11131221131211", "13211321", "311311", "11131", "1321133112", "31131112", "111312", "132", "311332", "1113222", "13221133112", "3113112221131112", "111312211312", "1321132", "311311222", "11131221133112", "1321131112", "311312", "11132", "13112221133211322112211213322113", "312211322212221121123222113", "111312211312113221133211322112211213322113", "1321132122211322212221121123222113", "3113112211322112211213322113", "111312212221121123222113", "132112211213322113", "31121123222113", "111213322113", "123222113", "3113322113", "1113222113", "1322113", "311311222113", "1113122113", "132113", "3113", "1113", "13", "3" ] def build_transition_matrix(): m = [[0] * K for _ in range(K)] for src in range(K): for j in range(DECAY_COUNT[src]): dst = DECAY[src][j] m[dst][src] += 1 return m def multiply_matrix(a, b): c = [[0] * K for _ in range(K)] for i in range(K): for k in range(K): if a[i][k] == 0: continue aik = a[i][k] for j in range(K): if b[k][j] == 0: continue c[i][j] = (c[i][j] + aik * b[k][j]) & MASK return c def apply_matrix(m, v): out = [0] * K for i in range(K): acc = 0 for j in range(K): if m[i][j] == 0 or v[j] == 0: continue acc += m[i][j] * v[j] out[i] = acc & MASK return out def evolve_vector(v, steps): power = build_transition_matrix() e = steps while e > 0: if e & 1: v = apply_matrix(power, v) e >>= 1 if e > 0: power = multiply_matrix(power, power) return v def solve(): v = [0] * K v[71] = 1 # Hf v[49] = 1 # Sn n = 1000000000000 v = evolve_vector(v, n - 8) digit_counts = [[0] * 3 for _ in range(K)] for i in range(K): for ch in ELEMENT_STRINGS[i]: if ch == '1': digit_counts[i][0] += 1 elif ch == '2': digit_counts[i][1] += 1 elif ch == '3': digit_counts[i][2] += 1 out = [0, 0, 0] for i in range(K): if v[i] == 0: continue for d in range(3): out[d] = (out[d] + v[i] * digit_counts[i][d]) & MASK return f"{out[0]},{out[1]},{out[2]}" if __name__ == '__main__': print(solve())