a506. CPE：LCM Pair Sum (UVa 12546)

題目描述

對正整數 n，考慮所有 1 ≤ p ≤ q ≤ n 且 lcm(p,q)=n 的配對，將每對的 p+q 相加，所得為 f(n)。例如 n=6 的配對為 (1,6)、(2,6)、(2,3)、(3,6)、(6,6)，所以 f(6)=41。給定 n 的質因數分解，求 f(n)。

輸入格式

第一行 T（T ≤ 500）。每筆先給質因數種類 C（正整數且 C ≤ 15），再給 C 行 Pi、ai，表示 n 含質因數 Pi 的 ai 次方。Pi 為 2 到 1000 的不同質數，1 ≤ ai ≤ 50。

輸出格式

每筆輸出 Case k: V，k 從 1 開始，V 為 f(n) 對 1000000007 取餘數。

題目來源：UVa 12546 — LCM Pair Sum，CPE 歷屆試題。 原題：https://onlinejudge.org/external/125/12546.pdf