Description

霸王龙得到五个整数，分别为k,l1,r1,l2,r2。霸王龙希望你帮他计算出满足以下所有条件的有序数对(x,y)的个数:
1. l1<=x<=r1
2. l2<=y<=r2
3. 存在一个非负整数n,使得y/x=kⁿ

Input Format

输入一行，包含五个整数，分别为  k ,l1,r1,l2,r2。
2<=k<=1e9。
1<=l1<=r1<=1e9。
1<=l2<=r2<=1e9。

Output Format

输出一个整数，表示满足所有条件的有序数对(x,y)的个数。

3 5 7 15 63

6

Hint

满足所有条件的有序数对有以下6个：(5,15)，(5,45)，(6,18)，(6,54)，(7,21)，(7,63)

Source

数论