问一道欧拉函数的模板题（我已经转化了一步题意）

Question

给定n,a,b，n<=1e7，求

原本的题意：

有一个 N*N 的矩阵，第 i 行第 j 列上的数字 Vi,j=GCD(Ai-Bi,Aj-Bj)，行和列的下标都从1开始，即1<=i,j<=N。

求矩阵里所有数字的和，即∑∑Vi,j。对1000000009取模。保证 A,B 互质

然后有一个性质，当a,b互质时:

题意就进一步转化了，不过我欧拉函数这一方面确实不好