描述

一个正整数如果能被 $a$ 或 $b$ 整除，那么它是神奇的。请你找一找第 $n$ 个神奇的数字。 (因为答案可能很大，所以返回答案对$10^9+7$取模后的值。)

输入格式

本题包含多 $（\le10^5）$ 组数据，每行一组数据。

每组数据包含3个正整数，分别表示 $n、a、b$。

输出格式

对于每组数据，在一行中输出一个整数表示答案。

样例

1 2 3
4 2 3

2
6

数据范围

$1\leq a,b\leq 10^9$

对于100%的数据，$1\leq n\leq 10^{19}$