a142. TOI 2025/09 潛力組：整數分拆

題目描述

把正整數 x 寫成一個或多個正整數的總和，並將各項相乘，所得數值稱為這次分拆的乘積。分拆允許只有一項，也允許重複的整數。請求出所有分拆中最大的乘積，再將它對 1000000007 取餘數。

輸入格式

第一行為詢問數 T；接下來 T 行各有一個正整數 x。

• 1 ≤ T ≤ 10000
• 1 ≤ x ≤ 10¹⁸

輸出格式

對每筆詢問輸出一行，表示最大乘積除以 1000000007 的餘數。

來源

TOI 2025 年 9 月潛力組〈整數分拆〉。本敘述重新撰寫；範例與測資為另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202509/partition.pdf