#2041. 「Cfz Round 1」Dead Cells

「Cfz Round 1」Dead Cells

题目描述

有一天,在第 00 个小时,一个细胞生成了,每过 aa 小时,细胞的数量就变成当前的两倍,每过 bb 小时,细胞的数量就变成当前的一半(向上取整)。

假如当前时间是 aa 和 bb 的公倍数,则细胞数量不变。问经过了 kk 小时后,细胞个数为多少,答案对 998244353998244353 取模。

输入格式

一行 33 个正整数,分别表示 a,b,ka,b,k。

输出格式

一行一个整数,表示答案。

样例

3 4 6
2
4 7 16
4
3 2 5
1
114 5141 919810
62166352

题目来源:洛谷 P9577