#P1445. [Violet] 樱花

[Violet] 樱花

题目背景

又到了一年樱花盛开的时节。Vani 和妹子一起去看樱花的时候,找到了一棵大大的樱花树,上面开满了粉红色的樱花。Vani 粗略估计了一下,一共有足足 n!n! 片花瓣。

Vani 轻柔地对她说:“你知道吗?这里面的一片花瓣代表着你,我从里面随机摘一片,能和你相遇的概率只有 1/n!1/n! 那么小。我该是多么的幸运,才让你今天这么近地站在我面前。相信我,我一定会把这亿万分之一的缘分变为永远。”

粉红的樱花漫天飞舞,妹子瞬间被 Vani 感动了。她轻轻地牵起了他的手,和他相依而坐。这时,她突然看到田野的尽头也长着两棵樱花树,于是慢慢地把头靠在 Vani 的肩上,在他耳边低语:“看到夕阳里的那两棵樱花树了吗?其中一棵树上的一片花瓣是你,另一棵树上的一片花瓣是我,如果有人从这棵摘下一片,从那棵采下一瓣,我们相遇的概率会不会正好是 1/n!1/n! 呢?”

Vani 的大脑飞速运作了一下,立即算出了答案。正要告诉妹子,她突然又轻轻地说:“以前你总是说我数学不好,但是这种简单的题我还是会算的。你看假如左边那棵树上有 xx 片花瓣,右边那个有 yy 片花瓣,那么我们相遇的概率不就是 1/x+1/y1/x+1/y 么,不过有多少种情况能使它正好可以等于 1/n!1/n! 呢?这个你就帮我算一下吧~”

显然,面对天然呆的可爱妹子,Vani 不但不能吐槽她的渣数学,而且还要老老实实地 帮她算出答案哦。

题目描述

求方程:

1x+1y=1n!\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{n!}

的正整数解的组数,答案对 109+710^9+7 取模。

输入格式

输入只有一行一个整数,表示 nn

输出格式

输出一行一个整数表示正整数解的组数模 109+710^9+7 的值。

2
3
1439
102426508

提示

样例 1 解释

共有三个数对 (x,y)(x,y) 满足条件,分别是 (3,6),(4,4)(3,6),(4,4)(6,3)(6,3)

数据规模与约定

  • 对于 30%30\% 的数据,保证 n100n\le 100
  • 对于 100%100\% 的数据,保证 1n1061 \le n\le 10^6