描述

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

输入格式

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

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

输出格式

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

样例

1 2 3
4 2 3

2
6

数据范围

$2\leq a,b\leq 10^4$ 对于100%的数据，$1\leq n\leq 10^9$