本题是 CF1646E 的加强版，题意与原题相同，唯一不同的是数据范围。

题意

已知一个 $n\times m$ 的表格，在 $(i,j)$ 上写有数字 $i^j$，求表格上有多少个不同的数字。

输入格式

一行两个数 $n,m$。

输出格式

一行一个数，表示答案。

3 3

7

2 4

5

4 2

6

1000000 1000000

999439867182

数据范围

对于 $10 \%$ 的数据，$n,m\le 1000$。

对于 $30 \%$ 的数据，$n,m\le 10^6$ （原题数据范围）。

对于 $60 \%$ 的数据，$n\le 10^9,m\le 10^6$。

对于 $100 \%$ 的数据，$n,m\le 10^9$。