P0410

模积和

模积和

模积和

给定两个正整数 n,mn, m，求

∑i=1n∑j=1j≠im((n mod i)×(m mod j)),\sum_{i=1}^{n}\sum_{\substack{j=1\\ j\ne i}}^{m}\bigl((n\bmod i)\times(m\bmod j)\bigr),

即对所有满足 1≤i≤n1\le i\le n、1≤j≤m1\le j\le m 且 i≠ji\ne j 的数对 (i,j)(i, j)，求 (n mod i)×(m mod j)(n\bmod i)\times(m\bmod j) 的和。

由于答案可能很大，你只需输出它对 1994041719940417 取模的结果。

输入格式

输入一行两个正整数 n,mn, m。

输出格式

输出一行一个整数，表示答案对 1994041719940417 取模的值。

样例输入

3 4

样例输出

1

样例解释

n=3n=3，m=4m=4，需要枚举的九个数对给出

(3 mod 1)(4 mod 2)+(3 mod 1)(4 mod 3)+(3 mod 1)(4 mod 4)+(3 mod 2)(4 mod 1)+(3 mod 2)(4 mod 3)+(3 mod 2)(4 mod 4)+(3 mod 3)(4 mod 1)+(3 mod 3)(4 mod 2)+(3 mod 3)(4 mod 4)=1,\begin{aligned} &(3\bmod 1)(4\bmod 2)+(3\bmod 1)(4\bmod 3)+(3\bmod 1)(4\bmod 4)\\ +{}&(3\bmod 2)(4\bmod 1)+(3\bmod 2)(4\bmod 3)+(3\bmod 2)(4\bmod 4)\\ +{}&(3\bmod 3)(4\bmod 1)+(3\bmod 3)(4\bmod 2)+(3\bmod 3)(4\bmod 4)\\ ={}&1, \end{aligned}

其中只有 (i,j)=(2,3)(i,j)=(2,3) 一项的贡献 1×11\times 1 非零。

数据范围

对于 100%100\% 的数据，1≤n,m≤1091\le n, m\le 10^9。

来源与许可

本题为中国国家队清华集训 2012-2013 第一天试题「模积和」，题面与测试数据整理自 BZOJ 2956。

样例 1

输入

3 4

输出

1